5.3. Describing Dynamic Software Updates

5.3.1. Describing Function Updates

At a minimum, the functions that will be updated need to defined. Figure 5-1 shows an example describing the updated functions when updating vsFTPd from version 2.0.4 to version 2.0.5.

#include "hcu_mappings.h"

hcu_mapping_update_description_t mapping_updates_v2[] = { { "main", "main" } };
hcu_mapping_function_update_description_t mapping_function_updates_v2[] = {
  { "str_locate_text_reverse", "str_locate_text_reverse", 0 },
  { "emit_greeting", "emit_greeting", 0 },
  { "handle_login", "handle_login", 0 },
  { "str_locate_chars", "str_locate_chars", 0 },
  { "vsf_privop_do_login", "vsf_privop_do_login", 0 },
  { "vsf_remove_uwtmp", "vsf_remove_uwtmp", 0 },
  { "handle_retr", "handle_retr", 0 },
  { "vsf_sysutil_connect_timeout", "vsf_sysutil_connect_timeout", 0 },
  { "handle_upload_common", "handle_upload_common", 0 },
  { "handle_user_command", "handle_user_command", 0 },
  { "main", "main", 1 },
  { "handle_mdtm", "handle_mdtm", 0 },
  { "handle_size", "handle_size", 0 },
  { "vsf_insert_uwtmp", "vsf_insert_uwtmp", 0 },
  { "handle_feat", "handle_feat", 0 },
  { "str_locate_text", "str_locate_text", 0 },
  { "get_unique_filename", "get_unique_filename", 0 },
  { "vsf_sysutil_chroot", "vsf_sysutil_chroot", 0 },
  { "vsf_sysdep_check_auth", "vsf_sysdep_check_auth", 0 },
  { "vsf_sysutil_tzset", "vsf_sysutil_tzset", 0 },
  { "handle_pass_command", "handle_pas_command", 0 },
  { "vsf_ls_populate_dir_list", "vsf_ls_populate_dir_list", 0 },
  { "calc_num_send", "calc_num_send", 0 },
  { "handle_stat", "handle_stat", 0 },
  { "vsf_privop_do_file_chown", "vsf_privop_do_file_chown", 0 }
};
           

• hcu_mapping_update_description_t

  This datatype defines an array of threads that should be updated. One variable declaration of this datatype is required.

  Since vsFTPd is a single-threaded program, this array contains only one entry. The entry requests that the thread called main (the thread whose entrypoint function is the function called main()) will have its stack reconstructed, when updated, all the way up to the function called main().

  It would be possible to request for this thread to be have its stack partially reconstructed, perhaps unwind up to one of the callees of the main() function instead of unwinding all the way up to the main() function. Perhaps this could be useful as an optimization that minimizes the updating latency in a deeply recursive program. But for most programs, unwinding the stack up to the thread entrypoint would have little effect in the total updating latency.

• hcu_mapping_function_update_description_t

  This datatype defines an array of functions that should be updated. One variable declaration of this datatype is required.

  Each definition of a function update consists of three fields. The name of the function that will be updated (from the original source code), the name of the function that will take its place (from the new source code), and a flag indicating whether the original function was a thread entrypoint.

  Thread entrypoints are the main() function, functions that are passed as arguments to a pthread_create(), and signal handlers defined with signal() and sigaction().

  Since vsFTPd is a single-threaded program, the entry to update the main() function is flagged as a thread entrypoint.

But wait! How did a user produce the list of function updates ? The patch generator, described in Section 5.4, can produce the list of modified functions when invoked with empty variable definitions of the two required datatypes hcu_mapping_update_description_t and hcu_mapping_function_update_description_t. It is expected that a user will first run the patch generator to produce the list of function updates, and then manually produce the update description file. But why ? Isn't the patch generator capable of producing the entire update description file ? The patch generator can produce the entire update description file, but that would be presumptuous. Producing the entire list of function updates in the file would guarantee that a program is representation consistent: the running version matches the source code. However, the user may not desire an update to be representation consistent for various reasons. A user may want to apply an update to only a small collection of functions. For example, the user may want to apply a security fix or avoid introducing, as part of the update, additional known defects that are present in the updated version of the program. Conclusion: Allowing users to manually produce a customized update description file separates policy from mechanism in the patch generator. There are plans to enhance the patch generator to produce a template update description file that the user may customize to produce the final file.

5.3.2. Describing Execution Continuation

UpStare is able to update a running algorithm midstream its execution and resume from a different point (not necessarily the beginning) of another algorithm that is behaviorally equivalent: an algorithm that aims to produce the same results while reusing existing progress. This capability requires user assistance. A user needs to define the mapping of update points in the original program to continuation points in the new version.

Figure 5-2 shows an example describing execution continuation when updating Bubblesort and continuing execution with Heapsort.

#include "hcu_mappings.h"
#include "hcu_headers.h"

hcu_mapping_update_description_t mapping_updates_v2[] = { { "main", "main" } };
hcu_mapping_function_update_description_t mapping_function_updates_v2[] = {
  { "main", "main", 1 }
};
hcu_mapping_algorithmic_equivalence_t mapping_equivalence_v2_bubblesort[] = {
  { "bubbleSort",
    "heapSort",
    1,
    { { 2, 1 } }
  }
};

struct hcu_stack_local_bubbleSort_v1_s {
   int i ;
   int j ;
   int temp ;
   struct hcu_stack_frame_fields_s hcu_stack_frame_fields ;
};

struct hcu_stack_local_heapSort_v2_s {
   int i ;
   int temp ;
   struct hcu_stack_frame_fields_s hcu_stack_frame_fields ;
};

struct hcu_function_formal_heapSort_v2_s {
   int *numbers ;
   int array_size ;
};

void HCU_stack_transformer__heapSort(void *transform_stack_to ,
                                     void *transform_stack_from ,
                                     void *transform_params_to ) 
{
  struct hcu_stack_local_heapSort_v2_s *stack_to ;
  struct hcu_stack_local_bubbleSort_v1_s *stack_from ;
  struct hcu_function_formal_heapSort_v2_s *params_to ;

  stack_to = (struct hcu_stack_local_heapSort_v2_s *)transform_stack_to;
  stack_from = (struct hcu_stack_local_bubbleSort_v1_s *)transform_stack_from;
  params_to = (struct hcu_function_formal_heapSort_v2_s *)transform_params_to;

  /* Continue the heapsort algorithm from the current iteration (redo
     the last iteration). Don't restart it from scratch.

     Our bubbleSort implementation processes an array from the
     end. Thus we simply have to shrink the array size to define the
     new bounds of the array for heapSort. */
  params_to->array_size = stack_from->i + 1;
  hcu_copy_stack_frame_fields(&stack_to->hcu_stack_frame_fields,
                              &stack_from->hcu_stack_frame_fields);
}
           

• hcu_mapping_algorithmic_equivalence_t

  This datatype defines an array of behaviorally equivalent functions.

  In each array element, the first parameter is the name of the function that will be updated, bubbleSort. The second parameter is the name of the behaviorally equivalent function from which execution will continue (heapSort) when it is time for the stack of the original function (bubbleSort) to be reconstructed. The third parameter reports the number of elements in the fourth parameter, which is an array. Each element of this array lists the update point number of the original function (update point 2 from bubbleSort) and a continuation point in the new function (heapSort) from which execution should resume. The continuation points in the new function are the same as the update points of the new function.

• void *transform_stack_to

  A pointer to the stack of the new function heapSort.

• void *transform_stack_from

  A pointer to the stack of the old function bubbleSort.

• void *transform_params_to

  A pointer to a struct variable that groups the formal parameters of the new function heapSort.

• hcu_copy_stack_frame_fields( from, to )

  Preserves the execution continuation point in the stack of the new function. Executing this function within a stack-state transformer is required.

So what happens in this example ? The stack of the updated function heapSort does not have state preserved from the stack of the old function bubbleSort at all. The stack of the old function is only consulted to change the formal parameters of the new function, and the stack of the new function remains uninitialized. Essentially, the new function continues execution by taking as input a smaller array of numbers to be sorted: it continues sorting from where Bubblesort stopped.