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: to unwind up to one of the callees of the main() function instead of unwinding all the way up to the main() function. 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.

5.3.3. Describing Update Constraints

Defining update constraints can help reduce the amount of state that needs to be mapped from the old version of an application to the new version. Depending on the updating model used, defining update constraints can also help enforce runtime safety.

If the updating model requested is to apply updates lazily, it is often necessary to define constraints that enforce type-safety and transaction-safety. The lazy updating model is enabled either using the HCU_STATIC_REQUEST_UPDATE_LAZY() call or by invoking the tool hcuapply with the command-line parameter--update-model=lazy.

Defining update constraints for type-safety is not necessary if the updating model requested is to apply updates immediately. However, defining update constraints for transaction-safety can be useful both for applying updates immediately and lazily.

Figure 5-3 shows an example describing update constraints.

#include "hcu_mappings.h"
#include "hcu_safety_constraints.h"

hcu_safety_constraint_t hcu_safety_constraints_v2[] = {
  { "main",
    "functionA",
    1,
    { { -1, -1, 0 } }
  }
};
           

• hcu_safety_constraints_t

  This datatype defines an array of update constraints.

  For each array element, the first parameter is the name of thread on which the constraints should be enforced. The second parameter is the name of function for the requested thread on which the constraints should be enforced. The third parameter is the number of elements in the fourth parameter. The fourth parameter is an array of update constraints in disjunctive normal form. For example, the constraint:

  (a|b)&c
                   

  should be expressed as:

  c&a|c&b
                   

  This means one should declare an array with two elements. In the first element one should add the two items: c a. In the second element one should add the two items: c b. For each constraint definition, there are three parameters

  • The minimum execution point allowed for a valid update. Execution must have passed this point to match the constraint.

    Note that a minimum of -1 is special and means anywhere (starting from the beginning of the function).

  • The maximum execution point allowed for a valid update. Execution must have not yet encountered this point to match the constraint.

    Note that a minimum of -1 is special and means anywhere (until the end of the function).

  • Whether this constraint is a negation (NOT).

So what happens in this example ? The constraint prohibits updates anywhere inside the function functionA for the main thread.