BoehmGC解読室 - 1 (small object の allocate)後編

(4)GENERAL_MALLOC

さて、(4)ではfreelistにhblkが無かった場合に新規に割り当てる関数が呼び出されています。
このマクロは以下の様な感じ。

#define GENERAL_MALLOC(lb,k) \
    GC_clear_stack(GC_generic_malloc(lb, k))
/* We make the GC_clear_stack_call a tail call, hoping to get more of	*/
/* the stack.								*/

 
GC_clear_stackはスタック上を綺麗にする関数のようです。(後で説明)
GC_generic_malloc関数に潜っていきましょうか。

void * GC_generic_malloc(size_t lb, int k)
{
    void * result;
    DCL_LOCK_STATE;

    if (GC_have_errors) GC_print_all_errors();
    GC_INVOKE_FINALIZERS();
    if (SMALL_OBJ(lb)) {
	LOCK();
        result = GC_generic_malloc_inner((word)lb, k);
	UNLOCK();
    } else {
/** 省略(big object用のコード) **/
    }
    if (0 == result) {
        return((*GC_oom_fn)(lb));
    } else {
        return(result);
    }
}

GC_generic_malloc_innerを呼んでるのか。くじけず潜る潜る。
 

GC_generic_malloc_inner
/* allocate lb bytes for an object of kind k.	*/
/* Should not be used to directly to allocate	*/
/* objects such as STUBBORN objects that	*/
/* require special handling on allocation.	*/
/* First a version that assumes we already	*/
/* hold lock:					*/
void * GC_generic_malloc_inner(size_t lb, int k)
{
    void *op;

    if(SMALL_OBJ(lb)) {

        /** [1] **/
        struct obj_kind * kind = GC_obj_kinds + k;
        size_t lg = GC_size_map[lb];
        void ** opp = &(kind -> ok_freelist[lg]);

        if( (op = *opp) == 0 ) {
            /** [2] **/
	    if (GC_size_map[lb] == 0) {
	      if (!GC_is_initialized)  GC_init_inner();
	      if (GC_size_map[lb] == 0) GC_extend_size_map(lb);
	      return(GC_generic_malloc_inner(lb, k));
	    }
            /** [3] **/
	    if (kind -> ok_reclaim_list == 0) {
	    	if (!GC_alloc_reclaim_list(kind)) goto out;
	    }
            /** [4] **/
	    op = GC_allocobj(lg, k);
	    if (op == 0) goto out;
        }
        *opp = obj_link(op);
        obj_link(op) = 0;
        GC_bytes_allocd += GRANULES_TO_BYTES(lg);
    } else {
/** 省略 **/
    }
    
out:
    return op;
}
[1]GC_obj_kinds

引数kにはNORMALが入ってます。

/* Predefined kinds: */
# define PTRFREE 0
# define NORMAL  1
# define UNCOLLECTABLE 2

extern struct obj_kind {
   void **ok_freelist;	/* Array of free listheaders for this kind of object */
   			/* Point either to GC_arrays or to storage allocated */
   			/* with GC_scratch_alloc.			     */
   struct hblk **ok_reclaim_list;
   			/* List headers for lists of blocks waiting to be */
   			/* swept.					  */
   			/* Indexed by object size in granules.		  */
   word ok_descriptor;  /* Descriptor template for objects in this	*/
   			/* block.					*/
   GC_bool ok_relocate_descr;
   			/* Add object size in bytes to descriptor 	*/
   			/* template to obtain descriptor.  Otherwise	*/
   			/* template is used as is.			*/
   GC_bool ok_init;   /* Clear objects before putting them on the free list. */
} GC_obj_kinds[MAXOBJKINDS];

GC_obj_kinds[1]を呼び出しているようです。
GC_obj_kindsは何か色々割当たってるみたいですね。
ここら辺は初期化で作成されたりしてるんですが、ま、いずれでてくるからいいか。
 

[2] if(GC_size_map[lb] == 0)
	    if (GC_size_map[lb] == 0) {
	      if (!GC_is_initialized)  GC_init_inner();
	      if (GC_size_map[lb] == 0) GC_extend_size_map(lb);
	      return(GC_generic_malloc_inner(lb, k));
	    }

size_mapから取り出したindexが0だった場合は、GC_init_innerで初期化したり、
GC_extend_size_mapでsize_mapを拡張して、再帰呼び出しします。
 

[3] if (kind -> ok_reclaim_list == 0)
            /** [3] **/
	    if (kind -> ok_reclaim_list == 0) {
	    	if (!GC_alloc_reclaim_list(kind)) goto out;
	    }

再利用可能なlistが無い場合、新規にメモリを割り当てます。
これは独自のmallocを作っていて、first-fitの戦略でやってるらしいっすが
書き出すと分量が多いので、また今度(といって逃げる)

[4] GC_allocobj
            /** [4] **/
	    op = GC_allocobj(lg, k);

この関数の中はこんな感じ。
 

/*
 * Make sure the object free list for size gran (in granules) is not empty.
 * Return a pointer to the first object on the free list.
 * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
 * Assumes we hold the allocator lock and signals are disabled.
 *
 */
ptr_t GC_allocobj(size_t gran, int kind)
{
    void ** flh = &(GC_obj_kinds[kind].ok_freelist[gran]);
    GC_bool tried_minor = FALSE;
    
    if (gran == 0) return(0);

    while (*flh == 0) {
      ENTER_GC();
      /* Do our share of marking work */
        if(TRUE_INCREMENTAL) GC_collect_a_little_inner(1);
      /* Sweep blocks for objects of this size */
        GC_continue_reclaim(gran, kind);
      EXIT_GC();
      if (*flh == 0) {
        GC_new_hblk(gran, kind);
      }
      if (*flh == 0) {
        ENTER_GC();
	if (GC_incremental && GC_time_limit == GC_TIME_UNLIMITED
	    && ! tried_minor ) {
	    GC_collect_a_little_inner(1);
	    tried_minor = TRUE;
	} else {
          if (!GC_collect_or_expand((word)1,FALSE)) {
	    EXIT_GC();
	    return(0);
	  }
	}
	EXIT_GC();
      }
    }
    /* Successful allocation; reset failure count.	*/
    GC_fail_count = 0;
    
    return(*flh);
}

ここは簡単に言うと

  • GC_continue_reclaim では sweep して、ok_reclaim_list から使えそうなhblkをfreelistに補充する
  • ダメだった場合
    • GC_new_hblkで新しいhblkを作成する
  • それでもダメな場合は
    • またGCを走らせる

そんな感じでしょうか。
 

結論

GENERAL_MALLOCはあの手この手で開いてるブロックを探したり、ダメだったら
新規に割り当てたりする。
 

徐々に

テケトーになっていってるような。
巨大過ぎてどこを詳細に説明しいいか分からないなぁ。
 

次回は

GC_clear_stackについて
(結構面白かった)