Lines Matching +full:fail +full:- +full:fast
20 AMIX edition, including the new compaction call-back option, prepared
23 Bug in built-in test program fixed, ANSI compiler warnings eradicated,
104 fragmentation. BGET is configured by compile-time definitions,
107 * A built-in test program to exercise BGET and
116 * Built-in routines to dump individual buffers or the
125 means of call-backs to user defined functions.
128 ROM-based embedded programs to providing the framework upon which
140 programs have obtained substantial speed-ups by layering BGET as
145 operating systems, multi-thread applications, embedded software in
148 years, it remains fast, memory efficient, portable, and easy to
182 ---------------------
195 ------------------
201 with bpool()--usually obtained by making a call to the operating
202 system's low-level memory allocator. Then allocate buffers with
204 of buffers initialised to zero and [inefficient] re-allocation of
212 ----------------------------
216 optionally application-specific memory compaction by compiling
222 does it?). Once the call-back functions have been defined with
234 compaction function again with the next-higher sequence number.
238 whether a non-NULL allocation function was supplied to bectl().
248 non-NULL release function is supplied, expansion blocks which
305 blocks when they become empty. If <compact> is non-NULL, whenever
316 attempt is re-tried. If <compact> returns 0 (as it must if it
319 pool expansion if the <acquire> argument is non-NULL. At the time
334 If <acquire> is non-NULL, that function will be called whenever an
339 and the entire allocation process will fail. <pool_incr>
342 large to be managed in the linked-block scheme (in other words,
357 filled, respectively, with the number of successful (non-NULL
416 #define TestProg 20000 /* Generate built-in test program
559 -1: not all pool blocks are
578 #define ESent ((bufsize) (-(((1L << (sizeof(bufsize) * 8 - 2)) - 1) * 2) - 2))
586 if (bf->bh.bsize < size) in buf_get_pos()
587 return -1; in buf_get_pos()
593 buf = (unsigned long)bf + bf->bh.bsize - size + sizeof(struct bhead) + in buf_get_pos()
595 buf &= ~(align - 1); in buf_get_pos()
596 pos = buf - (unsigned long)bf - sizeof(struct bhead) - hdr_size; in buf_get_pos()
603 return -1; in buf_get_pos()
608 struct bfhead *b = poolset->freelist.ql.flink; in get_free2_sum()
612 while (b != &poolset->freelist) { in get_free2_sum()
613 bs = b->bh.bsize; in get_free2_sum()
615 b = b->ql.flink; /* Link to next buffer */ in get_free2_sum()
622 * update_free2_sum() - cumulative update of the free^2 sum
643 assert(f2s == poolset->free2_sum - r2 + a2); in update_free2_sum()
644 assert(poolset->free2_sum >= r2); in update_free2_sum()
645 poolset->free2_sum -= r2; in update_free2_sum()
646 poolset->free2_sum += a2; in update_free2_sum()
650 /* BGET -- Allocate a buffer. */
685 if (ADD_OVERFLOW(size, SizeQuant - 1, &size))
705 b = poolset->freelist.ql.flink;
707 best = &poolset->freelist;
715 while (b != &poolset->freelist) {
716 assert(b->bh.prevfree == 0);
719 if ((best == &poolset->freelist) ||
720 (b->bh.bsize < best->bh.bsize)) {
724 b = b->ql.flink; /* Link to next buffer */
729 while (b != &poolset->freelist) {
733 struct bhead *b_next = BH((char *)b + b->bh.bsize);
734 bufsize rem_sz = b->bh.bsize;
737 assert(b_next->prevfree == b->bh.bsize);
743 b_next->prevfree = 0;
745 assert(b->ql.blink->ql.flink == b);
746 assert(b->ql.flink->ql.blink == b);
753 b->ql.blink->ql.flink = b->ql.flink;
754 b->ql.flink->ql.blink = b->ql.blink;
757 b->bh.bsize = -b->bh.bsize;
763 b_alloc->bsize = -(b->bh.bsize - pos);
764 b_alloc->prevfree = pos;
765 b->bh.bsize = pos;
769 assert(b_alloc->bsize < 0);
775 if (-b_alloc->bsize - size > SizeQ + sizeof(struct bhead)) {
782 b->bh.bsize = -b_alloc->bsize - size;
783 b->bh.prevfree = 0;
784 b_alloc->bsize += b->bh.bsize;
786 assert(poolset->freelist.ql.blink->ql.flink ==
787 &poolset->freelist);
788 assert(poolset->freelist.ql.flink->ql.blink ==
789 &poolset->freelist);
790 b->ql.flink = &poolset->freelist;
791 b->ql.blink = poolset->freelist.ql.blink;
792 poolset->freelist.ql.blink = b;
793 b->ql.blink->ql.flink = b;
795 assert(BH((char *)b + b->bh.bsize) == b_next);
796 b_next->prevfree = b->bh.bsize;
797 update_free2_sum(poolset, 0, 0, b->bh.bsize);
801 poolset->totalloc -= b_alloc->bsize;
802 poolset->numget++; /* Increment number of bget() calls */
807 b = b->ql.flink; /* Link to next buffer */
815 if ((poolset->compfcn == NULL) ||
816 (!(poolset->compfcn)(size, ++compactseq))) {
823 /* Don't give up yet -- look in the reserve supply. */
825 if (poolset->acqfcn != NULL) {
826 if (size > exp_incr - sizeof(struct bfhead) - align) {
832 size += sizeof(struct bdhead) - sizeof(struct bhead);
835 p = poolset->acqfcn(size);
846 tp &= ~(align - 1);
847 tp -= hdr_size;
849 bdh = BDH((char *)buf - sizeof(*bdh));
854 bdh->bh.bsize = 0;
855 bdh->bh.prevfree = 0;
856 bdh->tsize = size;
857 bdh->offs = (unsigned long)bdh - (unsigned long)p;
859 poolset->totalloc += size;
860 poolset->numget++; /* Increment number of bget() calls */
861 poolset->numdget++; /* Direct bget() call count */
872 if ((newpool = poolset->acqfcn((bufsize) exp_incr)) != NULL) {
888 /* BGETZ -- Allocate a buffer and clear its contents to zero. We clear
904 b = BH(buf - sizeof(struct bhead));
905 rsize = -(b->bsize);
909 bd = BDH(buf - sizeof(struct bdhead));
910 rsize = bd->tsize - sizeof(struct bdhead) - bd->offs;
912 rsize -= sizeof(struct bhead);
920 /* BGETR -- Reallocate a buffer. This is a minimal implementation,
942 b = BH(((char *) buf) - sizeof(struct bhead));
943 osize = -b->bsize;
949 bd = BDH(((char *) buf) - sizeof(struct bdhead));
950 osize = bd->tsize - sizeof(struct bdhead) - bd->offs;
953 osize -= sizeof(struct bhead);
960 V memset_unchecked((char *) nbuf + osize, 0, size - osize);
966 /* BREL -- Release a buffer. */
980 b = BFH(((char *) buf) - sizeof(struct bhead));
982 poolset->numrel++; /* Increment number of brel() calls */
990 if (b->bh.bsize == 0) { /* Directly-acquired buffer? */
993 bdh = BDH(((char *) buf) - sizeof(struct bdhead));
994 assert(b->bh.prevfree == 0);
996 poolset->totalloc -= bdh->tsize;
997 assert(poolset->totalloc >= 0);
998 poolset->numdrel++; /* Number of direct releases */
1002 (MemSize) (bdh->tsize -
1005 assert(poolset->relfcn != NULL);
1006 poolset->relfcn((char *)buf - sizeof(struct bdhead) - bdh->offs); /* Release it directly. */
1014 if (b->bh.bsize >= 0) {
1017 assert(b->bh.bsize < 0);
1022 assert(BH((char *) b - b->bh.bsize)->prevfree == 0);
1025 poolset->totalloc += b->bh.bsize;
1026 assert(poolset->totalloc >= 0);
1031 if (b->bh.prevfree != 0) {
1039 register bufsize size = b->bh.bsize;
1043 wipe_size = -size;
1046 assert(BH((char *) b - b->bh.prevfree)->bsize == b->bh.prevfree);
1047 b = BFH(((char *) b) - b->bh.prevfree);
1048 rem_sz = b->bh.bsize;
1049 b->bh.bsize -= size;
1050 add_sz = b->bh.bsize;
1057 assert(poolset->freelist.ql.blink->ql.flink == &poolset->freelist);
1058 assert(poolset->freelist.ql.flink->ql.blink == &poolset->freelist);
1059 b->ql.flink = &poolset->freelist;
1060 b->ql.blink = poolset->freelist.ql.blink;
1061 poolset->freelist.ql.blink = b;
1062 b->ql.blink->ql.flink = b;
1063 b->bh.bsize = -b->bh.bsize;
1064 update_free2_sum(poolset, 0, 0, b->bh.bsize);
1067 wipe_size = b->bh.bsize - sizeof(struct bfhead);
1075 bn = BFH(((char *) b) + b->bh.bsize);
1076 if (bn->bh.bsize > 0) {
1081 assert(BH((char *) bn + bn->bh.bsize)->prevfree == bn->bh.bsize);
1082 assert(bn->ql.blink->ql.flink == bn);
1083 assert(bn->ql.flink->ql.blink == bn);
1084 bn->ql.blink->ql.flink = bn->ql.flink;
1085 bn->ql.flink->ql.blink = bn->ql.blink;
1086 rem_sz = b->bh.bsize;
1087 rem_sz2 = bn->bh.bsize;
1088 b->bh.bsize += bn->bh.bsize;
1089 add_sz = b->bh.bsize;
1099 bn = BFH(((char *) b) + b->bh.bsize);
1106 assert(bn->bh.bsize < 0);
1111 bn->bh.prevfree = b->bh.bsize;
1115 /* If a block-release function is defined, and this free buffer
1117 is defined in such a way that the test will fail unless all
1120 if (poolset->relfcn != NULL &&
1121 ((bufsize) b->bh.bsize) == (pool_len - sizeof(struct bhead))) {
1123 assert(b->bh.prevfree == 0);
1124 assert(BH((char *) b + b->bh.bsize)->bsize == ESent);
1125 assert(BH((char *) b + b->bh.bsize)->prevfree == b->bh.bsize);
1127 b->ql.blink->ql.flink = b->ql.flink;
1128 b->ql.flink->ql.blink = b->ql.blink;
1130 poolset->relfcn(b);
1132 poolset->numprel++; /* Nr of expansion block releases */
1133 poolset->numpblk--; /* Total number of blocks */
1134 assert(numpblk == numpget - numprel);
1142 /* BECTL -- Establish automatic pool expansion control */
1151 poolset->compfcn = compact;
1152 poolset->acqfcn = acquire;
1153 poolset->relfcn = release;
1154 poolset->exp_incr = pool_incr;
1158 /* BPOOL -- Add a region of memory to the buffer pool. */
1169 len &= ~(SizeQuant - 1);
1172 if (poolset->pool_len == 0) {
1174 } else if (len != poolset->pool_len) {
1175 poolset->pool_len = -1;
1178 poolset->numpget++; /* Number of block acquisitions */
1179 poolset->numpblk++; /* Number of blocks total */
1180 assert(poolset->numpblk == poolset->numpget - poolset->numprel);
1188 assert(len - sizeof(struct bhead) <= -((bufsize) ESent + 1));
1194 b->bh.prevfree = 0;
1198 assert(poolset->freelist.ql.blink->ql.flink == &poolset->freelist);
1199 assert(poolset->freelist.ql.flink->ql.blink == &poolset->freelist);
1200 b->ql.flink = &poolset->freelist;
1201 b->ql.blink = poolset->freelist.ql.blink;
1202 poolset->freelist.ql.blink = b;
1203 b->ql.blink->ql.flink = b;
1213 len -= sizeof(struct bhead);
1214 b->bh.bsize = (bufsize) len;
1215 update_free2_sum(poolset, 0, 0, b->bh.bsize);
1218 (MemSize) (len - sizeof(struct bfhead)));
1221 bn->prevfree = (bufsize) len;
1223 assert((~0) == -1);
1224 bn->bsize = ESent;
1229 /* BSTATS -- Return buffer allocation free space statistics. */
1236 struct bfhead *b = poolset->freelist.ql.flink;
1238 *nget = poolset->numget;
1239 *nrel = poolset->numrel;
1240 *curalloc = poolset->totalloc;
1242 *maxfree = -1;
1243 while (b != &poolset->freelist) {
1244 assert(b->bh.bsize > 0);
1245 *totfree += b->bh.bsize;
1246 if (b->bh.bsize > *maxfree) {
1247 *maxfree = b->bh.bsize;
1249 b = b->ql.flink; /* Link to next buffer */
1255 /* BSTATSE -- Return extended statistics */
1262 *pool_incr = (poolset->pool_len < 0) ?
1263 -poolset->exp_incr : poolset->exp_incr;
1264 *npool = poolset->numpblk;
1265 *npget = poolset->numpget;
1266 *nprel = poolset->numprel;
1267 *ndget = poolset->numdget;
1268 *ndrel = poolset->numdrel;
1275 /* BUFDUMP -- Dump the data in a buffer. This is called with the user
1286 b = BFH(((char *) buf) - sizeof(struct bhead));
1287 assert(b->bh.bsize != 0);
1288 if (b->bh.bsize < 0) {
1290 bdlen = (-b->bh.bsize) - sizeof(struct bhead);
1293 bdlen = b->bh.bsize - sizeof(struct bfhead);
1306 V snprintf(bhex + i * 3, sizeof(bhex) - i * 3, "%02X ",
1311 V printf("%-48s %s\n", bhex, bascii);
1313 bdlen -= l;
1314 while ((bdlen > 16) && (memcmp((char *) (bdump - 16),
1318 bdlen -= 16;
1325 bdump -= 16;
1334 /* BPOOLD -- Dump a buffer pool. The buffer headers are always listed.
1346 while (b->bh.bsize != ESent) {
1347 bufsize bs = b->bh.bsize;
1350 bs = -bs;
1359 if ((b->ql.blink->ql.flink != b) ||
1360 (b->ql.flink->ql.blink != b)) {
1369 (MemSize) (bs - (sizeof(struct bfhead) + 1))) != 0))) {
1386 /* BPOOLV -- Validate a buffer pool. If NDEBUG isn't defined,
1394 while (b->bh.bsize != ESent) {
1395 bufsize bs = b->bh.bsize;
1398 bs = -bs;
1406 if ((b->ql.blink->ql.flink != b) ||
1407 (b->ql.flink->ql.blink != b)) {
1417 (MemSize) (bs - (sizeof(struct bfhead) + 1))) != 0))) {
1434 * Built-in test program *
1487 /* STATS -- Edit statistics returned by bstats() or bstatse(). */
1519 /* BCOMPACT -- Compaction call-back function. */
1546 i--;
1566 /* BEXPAND -- Expand pool call-back function. */
1583 V printf("Expand pool by %ld -- %s.\n", (long) size,
1589 /* BSHRINK -- Shrink buffer pool call-back function. */
1618 cool expression in sizeof(int) that auto-configured in blimit()
1650 p ranges from 0 to ExpIncr-1, with a concentration in the lower in bget_main_test()
1656 x = exp(log(4.0 * ExpIncr) / (ExpIncr - 1.0)); in bget_main_test()
1681 bufsize bs = pow(x, (double) (myrand() & (ExpIncr - 1))); in bget_main_test()
1683 bufsize bs = (myrand() & (ExpIncr * 4 - 1)) / (1 << (myrand() & 0x7)); in bget_main_test()
1729 assert(!align || !(((unsigned long)cb + hdr_size) & (align - 1))); in bget_main_test()
1742 j--; in bget_main_test()
1764 j--; in bget_main_test()
1774 bs = pow(x, (double) (myrand() & (ExpIncr - 1))); in bget_main_test()
1776 bs = (rand() & (ExpIncr * 4 - 1)) / (1 << (rand() & 0x7)); in bget_main_test()
1788 (align - 1))); in bget_main_test()