{"id":150,"date":"2014-07-15T08:44:55","date_gmt":"2014-07-15T08:44:55","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/?p=150"},"modified":"2015-07-13T11:42:12","modified_gmt":"2015-07-13T11:42:12","slug":"writing-functions-that-allocate-memory","status":"publish","type":"post","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/?p=150","title":{"rendered":"Writing functions that allocate memory"},"content":{"rendered":"

The purpose of this note is to explain how to write functions that allocate memory.\u00a0 One basic principle is that one should see the garbage collector<\/a> as an adversary, which always tries to deallocate memory.\u00a0 You should protect your data against it.\u00a0 Here are a few examples.<\/p>\n

The simplest case is that of a function that simply allocates a garbage-collectable data structure, and fills in some fields.\u00a0 Just use gc_alloc()<\/code>, as in the ovm_int_new()<\/code> function:<\/p>\n

ovm_var_t *ovm_int_new(gc_t *gc_ctx, long val)\r\n{\r\n\u00a0 ovm_int_t *n;\r\n\r\n\u00a0 n = gc_alloc (gc_ctx, sizeof (ovm_int_t), NULL);\r\n\u00a0 n->gc.type = T_INT;\r\n\u00a0 n->val = val;\r\n\u00a0 return OVM_VAR(n);\r\n}<\/pre>\n
 <\/p>\n
\n
 <\/p>\n
Now consider a slightly more complicated function: build_integer()<\/code> builds an object of type node_expr_t<\/code>, which holds a pointer in its data<\/code> field to an ovm_var_t<\/code> holding an integer.\u00a0 We need to allocate the ovm_var_t<\/code>, then the node_expr_t<\/code>, and store the former into the latter’s data<\/code> field.\u00a0 The garbage collector context is in ctx->gc_ctx<\/code>, so we might think of writing the following, but this is wrong.<\/p>\n
node_expr_t *build_integer(rule_compiler_t *ctx, int i)\r\n{\r\n\u00a0 ovm_var_t\u00a0\u00a0\u00a0 *integer;\r\n\u00a0 node_expr_term_t\u00a0 *n;\r\n\r\n\u00a0 integer = ovm_int_new(ctx->gc_ctx, i);\r\n\u00a0 n = (node_expr_term_t *) gc_alloc (ctx->gc_ctx, sizeof(node_expr_term_t),\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0 &node_expr_term_class);\r\n\u00a0 n->type = NODE_CONST;\r\n\u00a0 n->data = integer;\r\n\r\n\u00a0 return (node_expr_t *)n;\r\n}<\/pre>\n
Here is what goes wrong with this code snippet.\u00a0 The object integer<\/code> created by ovm_int_new()<\/code> is not pointed to by any data structure that the garbage collector can mark. The subsequent call to gc_alloc()<\/code><\/a> will invoke the garbage collector, to make sure some memory is deallocated, and might well deallocate the integer<\/code> object we have just allocated.<\/p>\n
This problem is nasty. In particular, gc_check()<\/code><\/a> has almost no way of detecting it.<\/p>\n
Oh, you might think that this will never happen, since the garbage collector would have to be damned quick to deallocate integer<\/code> this fast.<\/p>\n
Please never<\/strong>, never<\/strong> reason that way.\u00a0 You are right in thinking this will almost never happen, but this is precisely the problem: when the bug occurs (and be sure it will), it will be undiagnosable, irreproducible, impossible to debug, and will make Orchids fail in horrible ways.<\/p>\n
 <\/p>\n
\n
 <\/p>\n
Back to our problem: we need to protect integer<\/code> against the garbage collector. The standard solution is by using the GC_START<\/code>, GC_UPDATE<\/code>, and GC_END<\/code> macros:<\/p>\n
node_expr_t *build_integer(rule_compiler_t *ctx, int i)\r\n{\r\n  ovm_var_t    *integer;\r\n  node_expr_term_t  *n;\r\n\r\n  GC_START(ctx->gc_ctx, 1);\r\n  integer = ovm_int_new(ctx->gc_ctx, i);\r\n  GC_UPDATE(ctx->gc_ctx, 0, integer);\r\n\r\n  n = (node_expr_term_t *) gc_alloc (ctx->gc_ctx, sizeof(node_expr_term_t),\r\n\t\t\t\t     &node_expr_term_class);\r\n  n->type = NODE_CONST;\r\n  n->data = integer;\r\n\r\n  GC_END(ctx->gc_ctx);\r\n  return (node_expr_t *)n;\r\n}<\/pre>\n
The GC_START<\/code> macro allocates an array of protected entries on the C stack. You need to tell it how many entries this array will contain: 1 in our example. The entries are initialized to NULL<\/code>.\u00a0 We then use GC_UPDATE<\/code> to protect integer<\/code>, storing it at index 0 in the array.\u00a0 (But beware!\u00a0 This code still has problems.\u00a0 Read on.)<\/p>\n
Each call to GC_START<\/code> must be matched by exactly one call to GC_END<\/code>. To help check this, GC_START<\/code> expands to some piece of code that contains an open curly bracket ({<\/code>), and GC_END<\/code> contains the matching closing curly bracket (}<\/code>). Mismatches should be flagged by auto-indenting text editors.<\/p>\n
As a consequence, if your code is indented strangely, don’t dismiss that as a text formatting problem!\u00a0 It might be indicative of serious GC_START<\/code>\/GC_END<\/code> balancing bug.<\/p>\n
By the way, don’t try to be smart: call GC_START<\/code> at the beginning of your function with the right number of entries,\u00a0GC_END<\/code> at the end, and that’s it.<\/p>\n
And don’t use return<\/code> in the middle of your code, either. For example, the following is wrong:<\/p>\n
{\r\n  GC_START(gc_ctx, 3);\r\n  \/* do some stuff *\/\r\n  if (\/* somme error condition *\/)\r\n    return 1;\r\n  GC_END(gc_ctx);\r\n  return 0;\r\n}\r\n<\/pre>\n
This is wrong because the return 1<\/code> instruction will fail to execute the code hidden inside the GC_END<\/code> macro. Since this codes unlinks pointers stored on the stack, this will really cause havoc after return<\/code>.<\/p>\n
\n
Our latest attempt at writing build_integer()<\/code> is still wrong. This time, gc_check()<\/code><\/a> is more likely to spot the problem, but you’re safer if you don’t count on it.<\/p>\n
The problem is that the assignment n->data = integer<\/code> may violate the invariant that no black object points directly to a white object. You should use GC_TOUCH<\/code><\/a> to correct the problem, as follows:<\/p>\n
node_expr_t *build_integer(rule_compiler_t *ctx, int i)\r\n{\r\n  ovm_var_t    *integer;\r\n  node_expr_term_t  *n;\r\n\r\n  GC_START(ctx->gc_ctx, 1);\r\n  integer = ovm_int_new(ctx->gc_ctx, i);\r\n  GC_UPDATE(ctx->gc_ctx, 0, integer); \/* protect integer *\/\r\n\r\n  n = (node_expr_term_t *) gc_alloc (ctx->gc_ctx, sizeof(node_expr_term_t),\r\n\t\t\t\t     &node_expr_term_class);\r\n  n->type = NODE_CONST;\r\n  GC_TOUCH (ctx->gc_ctx, n->data = integer);\r\n\r\n  GC_END(ctx->gc_ctx);\r\n  return (node_expr_t *)n;\r\n}<\/pre>\n
In general, assignments of garbage-collectable objects should be enclosed in a call to GC_TOUCH<\/code>. The style exemplified above is recommended. In particular, don’t use the (equivalent) idiom:<\/p>\n
  n->data = integer; \/* suspicious assignement, may violate no-black-object-pointing-directly-to-white-object invariant *\/\r\n  GC_TOUCH (ctx->gc_ctx, n->data);<\/pre>\n
Code lines similar to n->data = integer<\/code>, without an enclosing GC_TOUCH<\/code>, should be seen as suspicious. You should always prefer the following style:<\/p>\n
  GC_TOUCH (ctx->gc_ctx, n->data = integer);<\/pre>\n
which makes it clear that the `no black object pointing directly to a white object’ invariant is satisfied.<\/p>\n
 <\/p>\n
\n
A final word (for today). One should protect data, not against gc_alloc()<\/code>, as would seem to be the case looking at the above example, but against any<\/em> function that may call the garbage collector.<\/p>\n
These include gc_alloc()<\/code>, gc()<\/code>, gc_full()<\/code>, but also gc_base_malloc()<\/code> and gc_base_realloc()<\/code> (which do ordinary C-style memory allocation and reallocation, but also call the garbage collector to be sure they will have enough memory), and all functions that call them directly or indirectly.<\/p>\n
As an illustration, here is the actual code for build_integer()<\/code>. The only difference with the above is that build_integer()<\/code> also adds integer<\/code> to a table of so-called static values, akin to Java’s constant pool, using statics_add()<\/code>. The latter may need to allocate some memory, and in that case will do it using gc_base_realloc()<\/code>. We therefore need to protect n<\/code> itself. The safest way is to use GC_UPDATE<\/code> again on it. Don’t forget to modify the call to GC_START<\/code> so that it allocates an array of 2 elements, not 1, this time:<\/p>\n
node_expr_t *build_integer(rule_compiler_t *ctx, int i)\r\n{\r\n  ovm_var_t    *integer;\r\n  node_expr_term_t  *n;\r\n\r\n  GC_START(ctx->gc_ctx, 2);\r\n  integer = ovm_int_new(ctx->gc_ctx, i);\r\n  GC_UPDATE(ctx->gc_ctx, 0, integer); \/* protect integer *\/\r\n\r\n  n = (node_expr_term_t *) gc_alloc (ctx->gc_ctx, sizeof(node_expr_term_t),\r\n\t\t\t\t     &node_expr_term_class);\r\n  n->type = NODE_CONST;\r\n  GC_TOUCH (ctx->gc_ctx, n->data = integer);\r\n  n->res_id = ctx->statics_nb;\r\n  GC_UPDATE(ctx->gc_ctx, 1, n); \/* protect n *\/\r\n\r\n  statics_add(ctx, integer);\r\n  GC_END(ctx->gc_ctx);\r\n  return (node_expr_t *)n;\r\n}\r\n<\/pre>\n
 <\/p>\n
\n
 <\/p>\n
Well, I’ve lied. This is not quite the actual code to build_integer()<\/code>. The actual code reuses slot 0 in the GC_START <\/code>array: integer<\/code> does not need to be stored there, since it will be protected by the data<\/code> field from the protected n<\/code> object.\u00a0 However, don’t try to be that smart. There are many ways to do smart things that will cause havoc with the garbage collector.<\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
The purpose of this note is to explain how to write functions that allocate memory.\u00a0 One basic principle is that one should see the garbage collector as an adversary, which always tries to deallocate memory.\u00a0 You should protect your data against it.\u00a0 Here are a few examples.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-150","post","type-post","status-publish","format-standard","hentry","category-memory-management"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/index.php?rest_route=\/wp\/v2\/posts\/150","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=150"}],"version-history":[{"count":8,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/index.php?rest_route=\/wp\/v2\/posts\/150\/revisions"}],"predecessor-version":[{"id":284,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/index.php?rest_route=\/wp\/v2\/posts\/150\/revisions\/284"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=150"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=150"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdev\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=150"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}