gdk_bbp.mx

这个是内存数据库中的一个管理工具

- too little memory: big bats are unloaded first (from LRU cold to hot).
Unloading-first is enforced by subtracting $2^31$ from the stamp in the
field where the candidates are sorted on.
@{
@c
#define BBPMAXTRIM 40000
#define BBPSMALLBAT 1000

typedef struct {
	int lastused;		/* bat lastused stamp; sort on this field */
	bat bid;		/* bat id */
	ssize_t cnt;		/* bat count */
	int next;		/* next position in list */
} bbptrim_t;

bbptrim_t bbptrim[BBPMAXTRIM];
int bbptrimfirst = BBPMAXTRIM, bbptrimlast = 0, bbpunloadtail, bbpunload, bbptrimmax = BBPMAXTRIM, bbpscanstart = 1;

static bat
BBPtrim_scan(int mem, int vm, bat bbppos, bat bbplim)
{
	bbptrimlast = 0;
	bbptrimmax = BBPMAXTRIM;
	MEMDEBUG THRprintf(GDKout, "#TRIMSCAN: mem=%d vm=%d, start=%d, limit=%d\n", mem, vm, (int) bbppos, (int) bbplim);

	if (bbppos < BBPsize)
		do {
			if (BBPvalid(bbppos)) {
				BAT *b = BBP_cache(bbppos);

				if (BBPtrimmable(b)) {
					/* when unloading for memory, treat small BATs with a preference over big ones.
					 * rationale: I/O penalty for cache miss is relatively higher for small bats 
					 */
					int swap_first = 0;
					ssize_t cnt = -1;

					if (b) {
						cnt = BATcount(b);
						swap_first = (cnt >= BBPSMALLBAT);
					}

					/* however, when we are looking to decrease the number of descriptors,
					 * try to put the small bats in front of the load list instead..
					 */

					/* subtract 2-billion to make sure the swap_first class bats are unloaded first */
					bbptrim[bbptrimlast].lastused = BBPLASTUSED(BBP_lastused(bbppos)) | (swap_first << 31);
					bbptrim[bbptrimlast].bid = bbppos;
					bbptrim[bbptrimlast].cnt = cnt;
					if (++bbptrimlast == bbptrimmax)
						break;
				}
			}
			if (++bbppos == BBPsize)
				bbppos = 1;	/* treat BBP as a circular buffer */
		} while (bbppos != bbplim);

	if (bbptrimlast > 0) {
		int i;
		GDKqsort(bbptrim, NULL, bbptrimlast, sizeof(bbptrim_t), TYPE_int, 0);
		for (i = bbptrimfirst = 0; i < bbptrimlast; i++) {
			MEMDEBUG THRprintf(GDKout, "#TRIMSCAN: %11d%c %9d=%s\t(#" SSZFMT ")\n", BBPLASTUSED(bbptrim[i].lastused), (bbptrim[i].lastused & 0x80000000) ? '*' : ' ', i, BBPname(bbptrim[i].bid), bbptrim[i].cnt);

			bbptrim[i].next = i + 1;
		}
		bbptrim[bbptrimlast - 1].next = BBPMAXTRIM;
	} else {
		bbptrimfirst = BBPMAXTRIM;
	}
	MEMDEBUG THRprintf(GDKout, "#TRIMSCAN: end at %d (size=%d)\n", bbppos, (int) BBPsize);

	return bbppos;
}


/* insert BATs to unload from bbptrim list into bbpunload list; rebuild bbptrimlist only with the useful leftovers */
static
    void
BBPtrim_select(size_t * memtarget, size_t * vmtarget, int dirty)
{
	int bbptrimtail = BBPMAXTRIM, next = bbptrimfirst;

	MEMDEBUG THRprintf(GDKout, "#TRIMSELECT: dirty = %d\n", dirty );

	/* make the bbptrim-list empty; we will insert the untouched elements in it */
	bbptrimfirst = BBPMAXTRIM;

	while (next != BBPMAXTRIM) {
		int cur = next;	/* cur is the entry in the old bbptrimlist we are processing */
		int untouched = BBPLASTUSED(BBP_lastused(bbptrim[cur].bid)) <= BBPLASTUSED(bbptrim[cur].lastused);
		BAT *b = BBP_cache(bbptrim[cur].bid);

		next = bbptrim[cur].next;	/* do now, because we overwrite bbptrim[cur].next below */

		MEMDEBUG if (b) {
			THRprintf(GDKout, "#TRIMSELECT: candidate=%s BAT*=" PTRFMT "\n", BBPname(bbptrim[cur].bid), PTRFMTCAST(void *)b);

			THRprintf(GDKout, "#            (cnt=" SSZFMT ", mode=%d, refs=%d, wait=%d, parent=%d, lastused=%d,%d,%d)\n", bbptrim[cur].cnt, b->batPersistence, BBP_refs(b->batCacheid), (BBP_status(b->batCacheid) & BBPWAITING) != 0, VIEWparent(b),
				  BBP_lastused(b->batCacheid), BBPLASTUSED(bbptrim[cur].lastused), bbptrim[cur].lastused);
		}
		/* recheck if conditions encountered by trimscan in the past still hold */
		if (BBPtrimmable(b) && untouched) {
			size_t memdelta = BATmemsize(b, FALSE);
			size_t vmdelta = BATvmsize(b, FALSE);
			size_t memdirty = BATmemsize(b, TRUE);
			size_t vmdirty = BATvmsize(b, TRUE);

			if (((b->batPersistence == TRANSIENT && BBP_lrefs(bbptrim[cur].bid) == 0) ||	/* needs not be saved when unloaded, OR.. */
			     (vmdirty == 0 && memdirty <= sizeof(BATstore)) ||	/* the BAT is actually clean, OR.. */
			     dirty)	/* we are allowed to cause I/O (second run).. */
			    &&	/* AND ... */
			    ((*memtarget > 0 && (memdelta > 0)) || (*vmtarget > 0 && (vmdelta > 0))))
			     /* there is some reward in terms of memory requirements */
			{
				/* only then we unload! */
				MEMDEBUG {
					THRprintf(GDKout, "#TRIMSELECT: unload %s [" SZFMT "," SZFMT "] bytes [" SZFMT "," SZFMT "] dirty\n", BBPname(b->batCacheid), memdelta, vmdelta, memdirty, vmdirty);
				}
				BBP_status_on(bbptrim[cur].bid, BBPUNLOADING, "BBPtrim_select");
				BBP_unload_inc(bbptrim[cur].bid, "BBPtrim_select"); 					
				*memtarget = *memtarget > memdelta ? *memtarget - memdelta : 0;
				*vmtarget = *vmtarget > vmdelta ? *vmtarget - vmdelta : 0;

				/* add to bbpunload list */
				if (bbpunload == BBPMAXTRIM) {
					bbpunload = cur;
				} else {
					bbptrim[bbpunloadtail].next = cur;
				}
				bbptrim[cur].next = BBPMAXTRIM;
				bbpunloadtail = cur;
			} else if (!dirty) {
				/* do not unload now, but keep around; insert at the end of the new bbptrim list */
				MEMDEBUG {
					THRprintf(GDKout, "#TRIMSELECT: keep %s [" SZFMT "," SZFMT "] bytes [" SZFMT "," SZFMT "] dirty target(mem=" SZFMT " vm=" SZFMT ")\n", BBPname(b->batCacheid), memdelta, vmdelta, memdirty, vmdirty, MAX(0, *memtarget), MAX(0, *vmtarget));
				}
				if (bbptrimtail == BBPMAXTRIM) {
					bbptrimfirst = cur;
				} else {
					bbptrim[bbptrimtail].next = cur;
				}
				bbptrim[cur].next = BBPMAXTRIM;
				bbptrimtail = cur;
			} else {
				/* bats that even in the second (dirty) run are not selected, should be acquitted from the trimlist until a next scan */
				MEMDEBUG THRprintf(GDKout, "#TRIMSELECT: delete %s from trimlist (does not match trim needs)\n", BBPname(bbptrim[cur].bid));
			}
		} else {
			/* BAT was touched (or unloaded) since trimscan =>  it is discarded from both lists */
			char buf[80], *bnme = BBP_logical(bbptrim[cur].bid);

			if (bnme == NULL) {
				bnme = BBPtmpname(buf, 64, bbptrim[cur].bid);
			}
			MEMDEBUG THRprintf(GDKout, "#TRIMSELECT: delete %s from trimlist (has been %s)\n", bnme, b ? "touched since last scan" : "unloaded already");
		}

		if (*memtarget == 0 && *vmtarget == 0) {
			/* we're done; glue the rest of the old bbptrim list to the new bbptrim list */
			if (bbptrimtail == BBPMAXTRIM) {
				bbptrimfirst = next;
			} else {
				bbptrim[bbptrimtail].next = next;
			}
			break;
		}
	}
	MEMDEBUG THRprintf(GDKout, "#TRIMSELECT: end\n");
}

extern int monet_exec(str);

void
BBPtrim(size_t memtarget, size_t vmtarget)
{
	int i, limit, scan, did_scan = FALSE;
	int msec = 0, bats_written = 0, bats_unloaded = 0;	/* performance info */
	MT_Id t = BBP_getpid();

	PERFDEBUG msec = GDKms();

	if (BBP_notrim == t)
		return;		/* avoid deadlock by one thread going here twice */

	gdk_set_lock(GDKtrimLock, "BBPtrim");
	BBP_notrim = t;

	/* recheck targets to see whether the work was already done by another thread */
	if (memtarget && memtarget != BBPTRIM_ALL) {
		memtarget = GDKmem_inuse();
		if (memtarget > GDK_mem_maxsize)
			memtarget -= GDK_mem_maxsize;
		else
			memtarget = 0;
	}
	if (vmtarget && vmtarget != BBPTRIM_ALL) {
		vmtarget = GDKvm_cursize();
		if (vmtarget > GDK_vm_maxsize)
			vmtarget -= GDK_vm_maxsize;
		else
			vmtarget = 0;
	}
	MEMDEBUG THRprintf(GDKout, "#BBPTRIM_ENTER: memsize=" SZFMT ",vmsize=" SZFMT "\n", GDKmem_inuse(), GDKvm_cursize());

	MEMDEBUG THRprintf(GDKout, "#BBPTRIM: memtarget=" SZFMT " vmtarget=" SZFMT "\n", memtarget, vmtarget );
	PERFDEBUG THRprintf(GDKout, "#BBPtrim(mem=%d,vm=%d)\n", memtarget > 0, vmtarget > 0 );

	scan = (bbptrimfirst == BBPMAXTRIM);
	if (bbpscanstart >= BBPsize)
		bbpscanstart = 1;	/* sometimes, the BBP shrinks! */
	limit = bbpscanstart;

	while (memtarget > 0 || vmtarget > 0) {
		/* acquire the BBP locks */
		gdk_set_lock(GDKcacheLock, "BBPtrim");
		for (i = 0; i <= BBPLOCKMASK; i++)
			gdk_set_lock(GDKswapLock[i & BBPLOCKMASK], "BBPtrim");

		/* gather a list of unload candidate BATs, but try to avoid scanning by reusing previous leftovers first */
		if (scan) {
			did_scan = TRUE;
			bbpscanstart = BBPtrim_scan((memtarget > 0), (vmtarget > 0), bbpscanstart, limit);
			scan = (bbpscanstart != limit);
		} else {
			scan = TRUE;
		}

		/* decide which of the candidates to unload using LRU */
		bbpunload = BBPMAXTRIM;
		BBPtrim_select(&memtarget, &vmtarget, FALSE);	/* first try to select only clean BATs */
		if (did_scan && (memtarget > 0 || vmtarget > 0)) {
			BBPtrim_select(&memtarget, &vmtarget, TRUE);	/* if that is not enough, also unload dirty BATs */
		}

		/* release the BBP locks */
		for (i = 0; i <= BBPLOCKMASK; i++)
			gdk_unset_lock(GDKswapLock[i & BBPLOCKMASK], "BBPtrim");
		gdk_unset_lock(GDKcacheLock, "BBPtrim");

		/* do the unload work unlocked */
		MEMDEBUG THRprintf(GDKout, "#BBPTRIM: %s\n", (bbpunload != BBPMAXTRIM) ? " lastused   batid name" : "no more unload candidates!");

		for (i = bbpunload; i != BBPMAXTRIM; i = bbptrim[i].next) {
			BAT *b = BBP_cache(bbptrim[i].bid);
			if (b == NULL || !(BBP_status(bbptrim[i].bid)&BBPUNLOADING)) {
				GDKwarning("BBPtrim: bat(%d) gone\n",  bbptrim[i].bid);
				continue;
			}
			MEMDEBUG THRprintf(GDKout, "#BBPTRIM: %9d %7d %s\n", bbptrim[i].lastused, (int) bbptrim[i].bid, BBPname(bbptrim[i].bid));

			bats_written += (b->batPersistence != TRANSIENT && BATdirty(b));
			bats_unloaded++;
			BBPfree(b, "BBPtrim" );
		}
		/* continue while we can scan for more candiates */
		if (!scan)
			break;
	}
	/* done trimming */
	MEMDEBUG THRprintf(GDKout, "#BBPTRIM_EXIT: memsize=" SZFMT ",vmsize=" SZFMT "\n", GDKmem_cursize(), GDKvm_cursize());
	PERFDEBUG THRprintf(GDKout, "#BBPtrim(did_scan=%d, bats_unloaded=%d, bats_written=%d) %d ms\n", did_scan, bats_unloaded, bats_written, GDKms() - msec);

	BBP_notrim = 0;
	gdk_unset_lock(GDKtrimLock, "BBPtrim");
}

void
BBPhot(bat i)
{
	if (i < 0)
		i = -i;
	if (BBPcheck(i, "BBPhot")) {
		int lock = locked_by ? BBP_getpid() != locked_by : 1;

		if (lock)
			gdk_set_lock(GDKswapLock[i & BBPLOCKMASK], "BBPhot");
		BBP_lastused(i) = BBPLASTUSED(BBPstamp() + 30000);
		if (lock)
			gdk_unset_lock(GDKswapLock[i & BBPLOCKMASK], "BBPhot");
	}
}

void
BBPcold(bat i)
{
	if (i < 0)
		i = -i;
	if (BBPcheck(i, "BBPcold")) {
		int lock = locked_by ? BBP_getpid() != locked_by : 1;

		gdk_set_lock(GDKtrimLock, "BBPcold");
		if (lock)
			gdk_set_lock(GDKswapLock[i & BBPLOCKMASK], "BBPcold");
		/* make very cold and insert on top of trim list */
		BBP_lastused(i) = 0;
		if (BBP_cache(i) && bbptrimlast < bbptrimmax) {
			bbptrim[--bbptrimmax].lastused = 0;
			bbptrim[bbptrimmax].bid = i;
			bbptrim[bbptrimmax].next = bbptrimfirst;
			bbptrimfirst = bbptrimmax;
		}
		if (lock)
			gdk_unset_lock(GDKswapLock[i & BBPLOCKMASK], "BBPcold");
		gdk_unset_lock(GDKtrimLock, "BBPcold");
	}
}

@}
@-
BBPquickdesc loads a BAT descriptor without loading the entire BAT, of which the
result be used only for a *limited* number of purposes. Specifically, during the 
global sync/commit, we do not want to load any BATs that are not already loaded, both 
because this costs performance, and because getting into memory shortage during a commit 
is extremely dangerous, as the global sync has all the BBPlocks, so no BBPtrim() can be 
done to free memory when needed. Loading a BAT tends not to be required, since the commit 
actions mostly involve moving some pointers in the BAT descriptor. However, some column 
types do require loading the full bat. This is tested by the complexatom() routine. Such 
columns are those of which the type has an fix/unfix method, or those that have HeapDelete
methods. The HeapDelete actions are not always required and therefore the BBPquickdesc
is parametrized.
@{
@c
static int
complexatom(int t, int delaccess)
{
	if (t >= 0 && (BATatoms[t].atomFix || (delaccess && BATatoms[t].atomDel))) {
		return TRUE;
	}
	return FALSE;
}

BAT *
BBPquickdesc(bat bid, int delaccess)
{
	BAT *b = BBP_cache(bid);

	if (bid < 0) {
		GDKerror("BBPquickdesc: called with negative batid.\n");
		return NULL;
	}
	if (b) {
		return b;	/* already cached */
	}
	b = (BAT *) BBPgetdesc(bid);
	if (b == NULL || 
	   complexatom(b->htype, delaccess) || 
	   complexatom(b->ttype, delaccess)) {
		b = BATload_intern(bid);
		BBPin++;
	}
	return b;
}

@}

@+ Small BAT Cache
@T
PETER: rewrote the batcache to make it stable with views and actually faster
       than allocating new bats (I guess that was the purpose of it)

this is tuned to minimizing the needed actions to get a BAT, in particular
we will do no BBPinsert, BUN dimension modifications, BATextends().

it also covers more cases, such as views and TYPE_str

main ideas:
- have [htpe,ttpe] specific lists to O(1) get a BAT from the desired type (bin-lists)
- implement LRU when the cache is full, with O(1) delete cost by using a fifo list
- keep bats in the BBP, as zombies (by invalidating their name)
- support views as void,void bats (they have in common that they lack heaps) 
- support TYPE_str as well, zapping their built-in string hash table
- only recycle BATTINY bats. Increase BATTINY to make more BATnews use the cache.
  BATTINY=256 leading to bunheaps ~1K-2K (in balance with ~500byte BAT record)

and then benchmark the d*mn thing (also missing in the previous exercise) :

module(alarm);
bbp_batcache_minsize(wrd(256));
{ var t := time(), i := 0; while((i :+= 1) < 100000) bat(int,int); print(time() - t); }
[ 490 ]
bbp_batcache_minsize(wrd(0));
{ var t := time(), i := 0; while((i :+= 1) < 100000) bat(int,int); print(time() - t); }
[ 847 ]

so with caching *some* MIL programs can be nearly twice as fast (optimized compile),
though I expect the gains to be smaller in general.
@{
@c
#define BATCACHE_NOTYPE(t) 	(ATOMstorage(t) > TYPE_str || BATatoms[t].atomFix != NULL)
#define BATCACHE_SIZE 		64 /* max size: 128 */ 
#define BATCACHE_DIMS 		6 /* 0,1,2,4,8 byte types + str */
#define BATCACHE_BIN(h,t) 	(batcache_headbin[ATOMstorage(h)]+batcache_tailbin[ATOMstorage(t)])

Dimensions batcache_dims;  	/* fast void,void bat dims initialization */
int batcache_headbin[TYPE_str+1], batcache_tailbin[TYPE_str+1]; /* fast bin computation */

typedef signed char batcache_int; /* make compact, whole structure is < 500 bytes: CPU cache resident  */

ssize_t batcache_minsize = BATTINY;

/* O(1) lookup structure of normalized [htype,ttype] combination (a "bin") */
static batcache_int  batcache_batbin  [BATCACHE_DIMS*BATCACHE_DIMS]; /* each bin starts a bin_next/prev list */
static unsigned char batcache_widthbin[BATCACHE_DIMS*BATCACHE_DIMS]; /* bun width */
static unsigned char batcache_locbin  [BATCACHE_DIMS*BATCACHE_DIMS]; /* tloc */

/* the list elements, use int as element pointer type (<0 means: no such element) */
typedef struct {
	bat bid;
	batcache_int bin_next, bin_prev; /* doubly linked list that connects all BATs for a bin */ 
	batcache_int fifo_next, fifo_prev; /* doubly linked list for getting the LRU BAT O(1) */
} batcache_t;
batcache_t batcache[BATCACHE_SIZE];

/* fifo queue */
static batcache_int batcache_first = -1; 
static batcache_int batcache_last = -1;

/* free list */
static batcache_int batcache_free = -1; /* misuses ->fifo_next for connecting the list */

static void
BBPinitcache(void)
{
	batcache_int i;
	int j;

	/* initialize struct for fast void,void header initialization */
        batcache_dims.headtype = batcache_dims.tailtype = TYPE_void;
        batcache_dims.headloc = batcache_dims.tailloc = 0;
        batcache_dims.headkey = batcache_dims.tailkey = FALSE;
        batcache_dims.headvarsized = batcache_dims.tailvarsized = TRUE;
        batcache_dims.bunshift = 0;
        batcache_dims.bunwidth = 1;
        batcache_dims.