erl_goodfit_alloc.c

OTP是开放电信平台的简称

}

static Block_t *
search_bucket(Allctr_t *allctr, int ix, Uint size)
{
    int i;
    Uint min_sz;
    Uint blk_sz;
    Uint cand_sz = 0;
    Uint max_blk_search;
    GFFreeBlock_t *blk;
    GFFreeBlock_t *cand = NULL;
    int blk_on_lambc;
    int cand_on_lambc = 0;
    GFAllctr_t *gfallctr = (GFAllctr_t *) allctr;

    ASSERT(0 <= ix && ix <= NO_OF_BKTS - 1);

    if (!gfallctr->buckets[ix])
	return NULL;

    min_sz = BKT_MIN_SZ(gfallctr, ix);
    if (min_sz < size)
	min_sz = size;

    max_blk_search = gfallctr->max_blk_search;
    for (blk = gfallctr->buckets[ix], i = 0;
	 blk && i < max_blk_search;
	 blk = blk->next, i++) {

	blk_sz = BLK_SZ(blk);
	blk_on_lambc = (((char *) blk) < gfallctr->last_aux_mbc_end
			&& gfallctr->last_aux_mbc_start <= ((char *) blk));

	if (blk_sz == min_sz && !blk_on_lambc)
	    return (Block_t *) blk;

	if (blk_sz >= min_sz
	    && (!cand
		|| (!blk_on_lambc && (cand_on_lambc || blk_sz < cand_sz))
		|| (blk_on_lambc && cand_on_lambc && blk_sz < cand_sz))) {
	    cand_sz = blk_sz;
	    cand = blk;
	    cand_on_lambc = blk_on_lambc;
	}

    }
    return (Block_t *) cand;
}

static Block_t *
get_free_block(Allctr_t *allctr, Uint size)
{
    GFAllctr_t *gfallctr = (GFAllctr_t *) allctr;
    int unsafe_bi, min_bi;
    Block_t *blk;

    unsafe_bi = BKT_IX(gfallctr, size);
    
    min_bi = find_bucket(&gfallctr->bucket_mask, unsafe_bi);
    if (min_bi < 0)
	return NULL;

    if (min_bi == unsafe_bi) {
	blk = search_bucket(allctr, min_bi, size);
	if (blk) {
	    unlink_free_block(allctr, blk);
	    return blk;
	}
	if (min_bi < NO_OF_BKTS - 1) {
	    min_bi = find_bucket(&gfallctr->bucket_mask, min_bi + 1);
	    if (min_bi < 0)
		return NULL;
	}
	else
	    return NULL;
    }
    else {
	ASSERT(min_bi > unsafe_bi);
    }

    /* We are guaranteed to find a block that fits in this bucket */
    blk = search_bucket(allctr, min_bi, size);
    ASSERT(blk);
    unlink_free_block(allctr, blk);
    return blk;
}



static void
link_free_block(Allctr_t *allctr, Block_t *block)
{
    GFAllctr_t *gfallctr = (GFAllctr_t *) allctr;
    GFFreeBlock_t *blk = (GFFreeBlock_t *) block;
    Uint sz = BLK_SZ(blk);
    int i = BKT_IX(gfallctr, sz);

    ASSERT(sz >= MIN_BLK_SZ);

    SET_BKT_MASK_IX(gfallctr->bucket_mask, i);

    blk->prev = NULL;
    blk->next = gfallctr->buckets[i];
    if (blk->next) {
	ASSERT(!blk->next->prev);
	blk->next->prev = blk;
    }
    gfallctr->buckets[i] = blk;
}

static void
unlink_free_block(Allctr_t *allctr, Block_t *block)
{
    GFAllctr_t *gfallctr = (GFAllctr_t *) allctr;
    GFFreeBlock_t *blk = (GFFreeBlock_t *) block;
    Uint sz = BLK_SZ(blk);
    int i = BKT_IX(gfallctr, sz);

    if (!blk->prev) {
	ASSERT(gfallctr->buckets[i] == blk);
	gfallctr->buckets[i] = blk->next;
    }
    else
	blk->prev->next = blk->next;
    if (blk->next)
	blk->next->prev = blk->prev;

    if (!gfallctr->buckets[i])
	UNSET_BKT_MASK_IX(gfallctr->bucket_mask, i);
}

static void
update_last_aux_mbc(Allctr_t *allctr, Carrier_t *mbc)
{
    GFAllctr_t *gfallctr = (GFAllctr_t *) allctr;

    if (gfallctr->last_aux_mbc_start != (char *) allctr->mbc_list.last) {

	if (allctr->mbc_list.last
	    && allctr->main_carrier != allctr->mbc_list.last) {
	    gfallctr->last_aux_mbc_start = (char *) allctr->mbc_list.last;
	    gfallctr->last_aux_mbc_end = (((char *) allctr->mbc_list.last)
					  + CARRIER_SZ(allctr->mbc_list.last));
	}
	else {
	    gfallctr->last_aux_mbc_start = NULL;
	    gfallctr->last_aux_mbc_end = NULL;
	}

    }
}

static struct {
    Eterm mbsd;
    Eterm as;
    Eterm gf;
#ifdef DEBUG
    Eterm end_of_atoms;
#endif
} am;

static void ERTS_INLINE atom_init(Eterm *atom, char *name)
{
    *atom = am_atom_put(name, strlen(name));
}
#define AM_INIT(AM) atom_init(&am.AM, #AM)

static void
init_atoms(void)
{
#ifdef DEBUG
    Eterm *atom;
#endif

    if (atoms_initialized)
	return;

#ifdef DEBUG
    for (atom = (Eterm *) &am; atom <= &am.end_of_atoms; atom++) {
	*atom = THE_NON_VALUE;
    }
#endif

    AM_INIT(mbsd);
    AM_INIT(as);
    AM_INIT(gf);

#ifdef DEBUG
    for (atom = (Eterm *) &am; atom < &am.end_of_atoms; atom++) {
	ASSERT(*atom != THE_NON_VALUE);
    }
#endif

    atoms_initialized = 1;
}

#define bld_uint	erts_bld_uint
#define bld_cons	erts_bld_cons
#define bld_tuple	erts_bld_tuple

static ERTS_INLINE void
add_2tup(Uint **hpp, Uint *szp, Eterm *lp, Eterm el1, Eterm el2)
{
    *lp = bld_cons(hpp, szp, bld_tuple(hpp, szp, 2, el1, el2), *lp);
}

static Eterm
info_options(Allctr_t *allctr,
	     char *prefix,
	     int *print_to_p,
	     void *print_to_arg,
	     Uint **hpp,
	     Uint *szp)
{
    GFAllctr_t *gfallctr = (GFAllctr_t *) allctr;
    Eterm res = THE_NON_VALUE;

    if (print_to_p) {
	erts_print(*print_to_p,
		   print_to_arg,
		   "%smbsd: %lu\n"
		   "%sas: gf\n",
		   prefix, gfallctr->max_blk_search,
		   prefix);
    }

    if (hpp || szp) {
	
	if (!atoms_initialized)
	    erl_exit(1, "%s:%d: Internal error: Atoms not initialized",
		     __FILE__, __LINE__);;

	res = NIL;
	add_2tup(hpp, szp, &res, am.as, am.gf);
	add_2tup(hpp, szp, &res,
		 am.mbsd,
		 bld_uint(hpp, szp, gfallctr->max_blk_search));
    }

    return res;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
 * NOTE:  erts_gfalc_test() is only supposed to be used for testing.         *
 *                                                                           *
 * Keep alloc_SUITE_data/allocator_test.h updated if changes are made        *
 * to erts_gfalc_test()                                                      *
\*                                                                           */

unsigned long
erts_gfalc_test(unsigned long op, unsigned long a1, unsigned long a2)
{
    switch (op) {
    case 0x100:	return (unsigned long) BKT_IX((GFAllctr_t *) a1, (Uint) a2);
    case 0x101:	return (unsigned long) BKT_MIN_SZ((GFAllctr_t *) a1, (int) a2);
    case 0x102:	return (unsigned long) NO_OF_BKTS;
    case 0x103:	return (unsigned long)
		    find_bucket(&((GFAllctr_t *) a1)->bucket_mask, (int) a2);
    default:	ASSERT(0); return ~((unsigned long) 0);
    }
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
 * Debug functions                                                           *
\*                                                                           */

#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
void
check_block(Allctr_t *allctr, Block_t * blk, int free_block)
{
    GFAllctr_t *gfallctr = (GFAllctr_t *) allctr;
    int i;
    int bi;
    int found;
    GFFreeBlock_t *fblk;

    if(free_block) {
	Uint blk_sz = BLK_SZ(blk);
	bi = BKT_IX(gfallctr, blk_sz);

	ASSERT(gfallctr->bucket_mask.main & (((Uint) 1) << IX2SMIX(bi)));
	ASSERT(gfallctr->bucket_mask.sub[IX2SMIX(bi)]
	       & (((Uint) 1) << IX2SBIX(bi)));
		
	found = 0;
	for (fblk = gfallctr->buckets[bi]; fblk; fblk = fblk->next)
	    if (blk == (Block_t *) fblk)
		found++;
	ASSERT(found == 1);
    }
    else
	bi = -1;

    found = 0;
    for (i = 0; i < NO_OF_BKTS; i++) {
	if (i == bi)
	    continue; /* Already checked */
	for (fblk = gfallctr->buckets[i]; fblk; fblk = fblk->next)
	    if (blk == (Block_t *) fblk)
		found++;
    }

    ASSERT(found == 0);

}

void
check_mbc(Allctr_t *allctr, Carrier_t *mbc)
{
    GFAllctr_t *gfallctr = (GFAllctr_t *) allctr;
    int bi;

    for(bi = 0; bi < NO_OF_BKTS; bi++) {
	if ((gfallctr->bucket_mask.main & (((Uint) 1) << IX2SMIX(bi)))
	    && (gfallctr->bucket_mask.sub[IX2SMIX(bi)]
		& (((Uint) 1) << IX2SBIX(bi)))) {
	    ASSERT(gfallctr->buckets[bi] != NULL);
	}
	else {
	    ASSERT(gfallctr->buckets[bi] == NULL);
	}
    }
}

#endif