nsd/dist/udb.c

55 chunk_get_last(void* base, udb_void chunk, int exp)
57 	return *((uint8_t*)UDB_REL(base, chunk+(1<<exp)-1));
63 chunk_set_last(void* base, udb_void chunk, int exp, uint8_t value)
65 	assert(exp >= 0 && exp <= 63);
66 	*((uint8_t*)UDB_REL(base, chunk+((uint64_t)1<<exp)-1)) = value;
640 	/* so, if exp zero bits then (o&(2**x-1))==0 */
690 regen_free(void* base, udb_void c, int exp, udb_alloc_d* regen)
693 	uint64_t esz = (uint64_t)1<<exp;
694 	if(exp < UDB_ALLOC_CHUNK_MINEXP || exp > UDB_ALLOC_CHUNKS_MAX) {
699 	chunk_set_last(base, c, exp, (uint8_t)exp);
701 	cp->next = regen->free[exp-UDB_ALLOC_CHUNK_MINEXP];
727 regen_data(void* base, udb_void c, int exp, udb_alloc_d* regen)
729 	uint64_t esz = (uint64_t)1<<exp;
730 	if(exp < UDB_ALLOC_CHUNK_MINEXP || exp > UDB_ALLOC_CHUNKS_MAX) {
733 	chunk_set_last(base, c, exp, (uint8_t)exp);
778 		int exp = (int)UDB_CHUNK(at)->exp;
780 		if(exp == UDB_EXP_XL) {
784 			at += (uint64_t)1<<exp;
787 			at += (uint64_t)1<<exp;
794 		int exp = (int)atp->exp;
796 		uint64_t sz = ((exp == UDB_EXP_XL)?UDB_XL_CHUNK(at)->size:
797 			(uint64_t)1<<exp);
798 		if(exp == UDB_EXP_XL) {
826 		UDB_CHUNK(q)->exp = UDB_ALLOC_CHUNKS_MAX;
897 	/* walk through the file, use the exp values to see what can be
924 		int exp = (int)UDB_CHUNK(at)->exp;
926 		/* consistency check possible here with end-exp */
928 			at = regen_free(base, at, exp, &regen);
930 		} else if(exp == UDB_EXP_XL) {
934 		} else if(exp >= UDB_ALLOC_CHUNK_MINEXP
935 			&& exp <= UDB_ALLOC_CHUNKS_MAX) {
937 			at = regen_data(base, at, exp, &regen);
997 udb_alloc_unlink_fl(void* base, udb_alloc* alloc, udb_void chunk, int exp)
1002 	assert(fp->exp == (uint8_t)exp);
1004 	assert(chunk_get_last(base, chunk, exp) == (uint8_t)exp);
1006 	assert(alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP]);
1010 	else	alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP] = fp->next;
1017 udb_alloc_pop_fl(void* base, udb_alloc* alloc, int exp)
1019 	udb_void f = alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP];
1022 	assert(fp->exp == (uint8_t)exp);
1024 	assert(chunk_get_last(base, f, exp) == (uint8_t)exp);
1025 	alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP] = fp->next;
1034 udb_alloc_push_fl(void* base, udb_alloc* alloc, udb_void f, int exp)
1038 	fp->exp = (uint8_t)exp;
1042 	fp->next = alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP];
1045 	chunk_set_last(base, f, exp, (uint8_t)exp);
1046 	alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP] = f;
1051 udb_alloc_push_fl_noinit(void* base, udb_alloc* alloc, udb_void f, int exp)
1055 	assert(fp->exp == (uint8_t)exp);
1057 	assert(chunk_get_last(base, f, exp) == (uint8_t)exp);
1059 	fp->next = alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP];
1062 	alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP] = f;
1084 /** append chunks at end of memory space to get size exp, return dataptr */
1086 grow_chunks(void* base, udb_alloc* alloc, size_t sz, int exp)
1088 	uint64_t esz = (uint64_t)1<<exp;
1095 	UDB_CHUNK(ret)->exp = (uint8_t)exp;
1100 	chunk_set_last(base, ret, exp, (uint8_t)exp);
1111 /** calculate how much space is necessary to grow for this exp */
1113 grow_end_calc(udb_alloc* alloc, int exp)
1115 	uint64_t sz = (uint64_t)1<<exp;
1120 		/* sz-1 is like 0xfff, and checks if ng is whole 2**exp */
1121 		return ng+sz; /* must grow exactly 2**exp */
1123 	/* grow until 2**expness and then we need 2**exp as well */
1172 /** grow space for a chunk of 2**exp and return dataptr */
1174 udb_alloc_grow_space(void* base, udb_alloc* alloc, size_t sz, int exp)
1183 	uint64_t grow_end = grow_end_calc(alloc, exp);
1187 		return grow_chunks(base, alloc, sz, exp);
1199 	return grow_chunks(base, alloc, sz, exp);
1216 	p->exp = UDB_EXP_XL;
1259 /** divide big(2**e2) into pieces so 2**exp fits */
1262 	int exp)
1266 	assert(big && e2 > exp);
1271 		e--;      /* that means its exp is one smaller */
1273 	} while(e != exp);
1283 	int exp;
1289 	exp = udb_exp_size(asz);
1290 	assert(exp <= UDB_ALLOC_CHUNKS_MAX);
1291 	return exp;
1298 	int e2, exp = udb_alloc_exp_needed(sz);
1299 	if(exp == UDB_EXP_XL)
1302 	if(alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP]) {
1306 		ret = udb_alloc_pop_fl(base, alloc, exp);
1313 		alloc->disk->stat_alloc += (1<<exp);
1314 		assert(alloc->disk->stat_free >= (1u<<exp));
1315 		alloc->disk->stat_free -= (1<<exp);
1320 	for(e2 = exp+1; e2 <= UDB_ALLOC_CHUNKS_MAX; e2++)
1326 			ret = udb_alloc_subdivide(base, alloc, big, e2, exp);
1328 			UDB_CHUNK(ret)->exp = (uint8_t)exp;
1329 			/* if stop here; the new exp makes smaller free chunk*/
1335 			chunk_set_last(base, ret, exp, (uint8_t)exp);
1338 			alloc->disk->stat_alloc += (1<<exp);
1339 			assert(alloc->disk->stat_free >= (1u<<exp));
1340 			alloc->disk->stat_free -= (1<<exp);
1345 	return udb_alloc_grow_space(base, alloc, sz, exp);
1350 have_free_for(udb_alloc* alloc, int exp)
1353 	if(alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP])
1354 		return exp;
1355 	for(e2 = exp+1; e2 <= UDB_ALLOC_CHUNKS_MAX; e2++)
1400 move_chunk(void* base, udb_alloc* alloc, udb_void f, int exp, uint64_t esz,
1406 	if(exp != e2) {
1408 		res = udb_alloc_subdivide(base, alloc, res, e2, exp);
1415 	/* take the res, exp into use */
1435 		assert(UDB_CHUNK(q)->exp == UDB_ALLOC_CHUNKS_MAX);
1486 		assert(xlp->exp == UDB_EXP_XL);
1502 coagulate_possible(void* base, udb_alloc* alloc, udb_void f, int exp,
1506 	if(exp == UDB_ALLOC_CHUNKS_MAX)
1514 		/* the header is also protected by the special exp marker */
1521 		if(*((uint8_t*)UDB_REL(base, f-1)) == (uint8_t)exp) {
1523 			assert(UDB_FREE_CHUNK(other)->exp == (uint8_t)exp);
1528 		if(UDB_CHUNK(other)->exp == (uint8_t)exp) {
1530 			assert(chunk_get_last(base, other, exp)==(uint8_t)exp);
1540 coagulate_and_push(void* base, udb_alloc* alloc, udb_void last, int exp,
1545 	while( (other=coagulate_possible(base, alloc, last, exp, esz)) ) {
1547 		udb_alloc_unlink_fl(base, alloc, other, exp);
1551 		exp++;
1555 	udb_alloc_push_fl(base, alloc, last, exp);
1564 	int exp, e2;
1574 		exp = (int)*((uint8_t*)UDB_REL(base, at-1));
1575 		if(exp == UDB_EXP_XL) {
1585 			assert(xlp->exp == UDB_EXP_XL);
1605 		} else if(exp < UDB_ALLOC_CHUNK_MINEXP
1606 			|| exp > UDB_ALLOC_CHUNKS_MAX)
1608 		esz = (uint64_t)1<<exp;
1610 		assert(UDB_CHUNK(last)->exp == (uint8_t)exp);
1617 				udb_alloc_unlink_fl(base, alloc, last, exp);
1624 		} else if( (e2=have_free_for(alloc, exp)) ) {
1628 			move_chunk(base, alloc, last, exp, esz, e2);
1631 					last, exp, esz);
1666 			assert(UDB_CHUNK(chunk)->exp==UDB_ALLOC_CHUNKS_MAX);
1756 	int exp;
1777 	if(fp->exp == UDB_EXP_XL) {
1786 	/* it is a regular chunk of 2**exp size */
1787 	exp = (int)fp->exp;
1788 	esz = (uint64_t)1<<exp;
1791 	assert(chunk_get_last(base, f, exp) == (uint8_t)exp);
1805 	while( (other=coagulate_possible(base, alloc, f, exp, esz)) ) {
1808 		udb_alloc_unlink_fl(base, alloc, other, exp);
1812 		exp++;
1817 		udb_alloc_push_fl(base, alloc, f, exp);
1819 		/* we do not need to touch the last-exp-byte, which may save
1823 		udb_alloc_push_fl_noinit(base, alloc, f, exp);
1861 	if(cp->exp == UDB_EXP_XL) {
1865 		avail = ((uint64_t)1<<cp->exp) - sizeof(udb_chunk_d) - 1;
1890 	int exp = udb_alloc_exp_needed(sz);
1893 	if(exp == UDB_EXP_XL)
1895 	else	esz = (uint64_t)1<<exp;
1897 	want = grow_end_calc(alloc, exp) + esz*(num-1);
1930 	int exp;
1940 	exp = UDB_CHUNK(ch)->exp;
1941 	if(exp == UDB_EXP_XL) {
1957 	if(exp < UDB_ALLOC_CHUNK_MINEXP || exp > UDB_ALLOC_CHUNKS_MAX)
1959 	esz = 1<<exp;
1962 	if(*((uint8_t*)UDB_REL(base, ch+esz-1)) != exp)