#include <assert.h>
-#include <stdio.h> // temporary
+#include <stdarg.h>
+//#include <stdio.h> // temporary
#include <stdlib.h>
#include "pool.h"
-// can only define TRY_BLOCKER if MOVEABLE_POOL also defined
#define MOVEABLE_POOL 1
#define TRY_BLOCKER 1
check_invariants(head);
#endif
}
-
-bool pool_realloc(
+
+bool pool_alloc(
struct pool_head *head,
struct pool_item *item,
int size,
- int offset,
- bool dir
+ int mode,
+ ...
) {
- int old_size, new_base, new_limit;
- int end_offset;
- int size_change, avail, gap;
- bool orig_dir;
+ int size_change, gap;
+ va_list ap;
+ int new_base, new_limit, avail;
+ bool dir;
struct pool_item *p, *q;
-#ifdef TRY_BLOCKER
+#if defined(MOVEABLE_POOL) && defined(TRY_BLOCKER)
struct pool_item *r, *target_item;
int target_size;
- bool prev_next;
#endif
- int old_base_truncated, new_base_offset;
- int old_limit_truncated, new_limit_offset;
+ int base_offset, limit_offset;
// see if request is for "alloc" or "realloc"
- old_size = 0;
- if (offset != INT_MIN) {
+ size_change = size;
+ if (mode & POOL_ALLOC_MODE_REALLOC) {
// realloc, item must be already allocated
assert(item->prev && item->next);
- old_size = item->limit - item->base;
+ size_change += item->base - item->limit;
// calculate new spot if block is extended not moved
- new_base = item->base - offset;
- new_limit = new_base + size;
-#ifndef TRY_BLOCKER
+ gap = 0;
+ if (mode & POOL_ALLOC_MODE_REALLOC_OFFSET) {
+ va_start(ap, mode);
+ gap = va_arg(ap, int);
+ va_end(ap);
+ }
+ if ((mode & POOL_ALLOC_MODE_LAST_FIT) == 0) {
+ new_base = item->base - gap;
+ new_limit = new_base + size;
+ }
+ else {
+ new_limit = item->limit - gap;
+ new_base = new_limit - size;
+ }
+#if !defined(MOVEABLE_POOL) || !defined(TRY_BLOCKER)
if (new_base >= item->prev->limit && new_limit <= item->next->base)
goto resize;
#endif
#endif
// check size, disregarding fragmentation
- size_change = size - old_size;
avail = head->avail - size_change;
if (avail < 0)
return false;
// work in specified direction, then reverse
- orig_dir = dir;
+ dir = (mode & POOL_ALLOC_MODE_LAST_FIT) != 0;
while (true) {
p = &head->item;
q = &head->item;
-#ifdef TRY_BLOCKER
+#if defined(MOVEABLE_POOL) && defined(TRY_BLOCKER)
blocker_test:
// enter here when either blocker has changed
target_item = item;
target_size = size;
//printf("a target_size %d\n", target_size);
- if (offset != INT_MIN) {
+ if (mode & POOL_ALLOC_MODE_REALLOC) {
if (new_base >= item->prev->limit && new_limit <= item->next->base)
goto resize;
- r = item->prev;
- prev_next = false;
- do {
+ if (mode & POOL_ALLOC_MODE_MOVEABLE) {
+ // check both blockers to see if smaller than item
+ r = item->prev;
if (new_base < r->limit && r != &head->item) {
gap = r->limit - r->base;
if (gap < target_size) {
//printf("b target_size %d\n", target_size);
}
}
+
r = item->next;
- prev_next = !prev_next;
- } while (prev_next);
+ if (new_limit > r->base && r != &head->item) {
+ gap = r->limit - r->base;
+ if (gap < target_size) {
+ target_item = r;
+ target_size = gap;
+ //printf("c target_size %d\n", target_size);
+ }
+ }
+ }
}
#endif
if (!dir) {
p = q;
q = p->next;
-//#ifdef TRY_BLOCKER
-// if (q == item || q == target_item) {
-//#else
if (q == item) {
-//#endif
+ // skip our own item for gap calculation
q = q->next;
- break;
+
+#ifdef MOVEABLE_POOL
+ // if non-moveable, do our own item specially then reverse direction
+ if (mode & POOL_ALLOC_MODE_MOVEABLE)
+ break;
+#endif
}
//printf("forw %p(%d)->%p(%d)\n", p, p->limit, q, q->base);
}
else {
q = p;
p = q->prev;
-//#ifdef TRY_BLOCKER
-// if (p == item || p == target_item) {
-//#else
if (p == item) {
-//#endif
+ // skip our own item for gap calculation
p = p->prev;
- break;
+
+#ifdef MOVEABLE_POOL
+ // if non-moveable, do our own item specially then reverse direction
+ if (mode & POOL_ALLOC_MODE_MOVEABLE)
+ break;
+#endif
}
//printf("back %p(%d)->%p(%d)\n", p, p->limit, q, q->base);
}
// see if target fits in current gap
gap = q->base - p->limit;
-#ifdef TRY_BLOCKER
+#if defined(MOVEABLE_POOL) && defined(TRY_BLOCKER)
if (target_size <= gap) {
//printf("target\n");
if (target_item == item)
goto found;
+
+ assert(mode & POOL_ALLOC_MODE_MOVEABLE);
if (!dir) {
- if (!head->move)
- goto no_blocker;
+ assert(head->move);
head->move(target_item, p->limit);
target_item->limit += p->limit - target_item->base;
target_item->base = p->limit;
}
else {
- if (!head->move_up)
- goto no_blocker;
+ assert(head->move_up);
head->move_up(target_item, q->base);
target_item->base += q->base - target_item->limit;
target_item->limit = q->base;
p = target_item;
q = target_item;
goto blocker_test;
-
- no_blocker:
- ;
}
#else
if (size <= gap)
avail -= gap;
if (avail < 0) {
#ifdef MOVEABLE_POOL
+ if (!(mode & POOL_ALLOC_MODE_MOVEABLE))
+ return false;
+ avail += gap;
+
//printf("compact\n");
if (!dir) {
- if (!head->move)
-#ifndef NDEBUG
- {
- check_invariants(head);
-#endif
- return false;
-#ifndef NDEBUG
- }
-#endif
+ assert(head->move);
head->move(q, p->limit);
q->limit += p->limit - q->base;
q->base = p->limit;
}
else {
- if (!head->move_up)
-#ifndef NDEBUG
- {
- check_invariants(head);
-#endif
- return false;
-#ifndef NDEBUG
- }
-#endif
+ assert(head->move_up);
head->move_up(p, q->base);
p->base += q->base - p->limit;
p->limit = q->base;
}
- avail += gap;
// if we have just moved the target, then the target is
// no longer valid and we should go to blocker_test, but
dir = !dir;
//printf("dir changed to %d\n", dir);
- assert(dir != orig_dir);
+ assert(dir != ((mode & POOL_ALLOC_MODE_LAST_FIT) != 0));
}
found:
//printf("found\n");
+ // before clobbering the in-place position calculation,
+ // figure out how much each end is truncated or extended
+ // (if non-zero, one of these was passed as a parameter)
+ base_offset = item->base - new_base;
+ limit_offset = item->limit - new_limit;
+
// align ourself in found spot
// (try to allow future extension in desired direction)
- if (orig_dir == false) {
+ if ((mode & POOL_ALLOC_MODE_LAST_FIT) == 0) {
new_base = p->limit;
new_limit = new_base + size;
}
new_base = new_limit - size;
}
- if (offset != INT_MIN) {
+ if (mode & POOL_ALLOC_MODE_REALLOC) {
// move ourself into found spot
-
- // we have "offset", which is position of start of existing data
- // relative to start of new block, now calculate symmetric one:
- // position of end of existing data relative to end of new block
- // (new_limit + end_offset) - (new_base + offset) = old_size
- // (new_limit - new_base) + (end_offset - offset) = old_size
- // size + end_offset - offset = old_size
- // end_offset = offset - (size - old_size)
- end_offset = offset - size_change;
-
- old_base_truncated = item->base;
- new_base_offset = new_base;
- if (offset < 0)
- // copy truncated start of old block to base of new block
- old_base_truncated -= offset;
- else
- // copy original start of old block to offset in new block
- new_base_offset += offset;
-
- old_limit_truncated = item->limit;
- new_limit_offset = new_limit;
- if (end_offset >= 0)
- // copy truncated end of old block to limit of new block
- old_limit_truncated -= end_offset;
- else
- // copy original end of old block to offset in new block
- new_limit_offset += end_offset;
-
- offset = new_base_offset - old_base_truncated; // amount to move by
- if (offset < 0) {
- if (!head->move)
-#ifndef NDEBUG
- {
- check_invariants(head);
-#endif
- return false;
-#ifndef NDEBUG
- }
-#endif
- item->base = old_base_truncated;
- item->limit = old_limit_truncated;
- head->move(item, new_base_offset);
- }
- else if (offset > 0) {
- if (!head->move_up)
-#ifndef NDEBUG
- {
- check_invariants(head);
-#endif
- return false;
-#ifndef NDEBUG
- }
-#endif
- item->base = old_base_truncated;
- item->limit = old_limit_truncated;
- head->move_up(item, new_limit_offset);
+ // (throw away truncated parts before calling move routine)
+
+ // in certain cases there can't be truncation, and we can also
+ // guarantee the overlap direction, so prefer the move routine
+ // for given direction (user doesn't need to provide other one)
+ switch (mode) {
+ case POOL_ALLOC_MODE_REALLOC:
+ assert(head->move);
+ head->move(item, new_base);
+ break;
+ case POOL_ALLOC_MODE_LAST_FIT | POOL_ALLOC_MODE_REALLOC:
+ assert(head->move_up);
+ head->move_up(item, new_limit);
+ break;
+ default:
+ assert(head->move && head->move_up);
+ if (base_offset < 0) {
+ item->base -= base_offset;
+ base_offset = 0;
+ }
+ if (limit_offset > 0) {
+ item->limit -= limit_offset;
+ limit_offset = 0;
+ }
+ base_offset += new_base;
+ gap = base_offset - item->base; // amount to move by
+ if (gap < 0)
+ head->move(item, base_offset);
+ else if (gap > 0)
+ head->move_up(item, limit_offset + new_limit);
}
// remove from list
resize:
//printf("fits %p(%d)->%p(%d) [%d,%d)\n", item->prev, item->prev->limit, item->next, item->next->base, new_base, new_limit);
- // resize in place
item->base = new_base;
item->limit = new_limit;
}
int n_items = atoi(argv[1]);
int pool_size = atoi(argv[2]);
- bool dir = argc >= 4 ? strcmp(argv[3], "false") != 0 : false;
- bool moveable = argc >= 5 ? strcmp(argv[4], "false") != 0 : false;
- printf("dir %d moveable %d\n", dir, moveable);
+ int mode = 0;
+ if (argc >= 4 && strcmp(argv[3], "false") != 0)
+ mode |= POOL_ALLOC_MODE_LAST_FIT;
+ if (argc >= 5 && strcmp(argv[4], "false") != 0)
+ mode |= POOL_ALLOC_MODE_MOVEABLE;
struct pool_head head;
- pool_init(
- &head,
- 0,
- pool_size,
- moveable || !dir ? move : NULL,
- moveable || dir ? move_up : NULL
- );
+ pool_init(&head, 0, pool_size, move, move_up);
struct pool_item *items = malloc(n_items * sizeof(struct pool_item));
rassert(items);
success ? "true" : "false"
);
rassert(items[item].prev == NULL);
- bool result = pool_alloc(&head, items + item, size, dir);
+ bool result = pool_alloc(&head, items + item, size, mode);
printf(
"... %s\n",
result == success ?
actual_old_size - size,
size
);
- bool result = pool_realloc(&head, items + item, size, 0, dir);
+ bool result = pool_alloc(
+ &head,
+ items + item,
+ size,
+ mode | POOL_ALLOC_MODE_REALLOC
+ );
printf(
"... %s\n",
result == success ?
if (result) {
if (!success) {
printf("... undo\n");
- rassert(pool_realloc(&head, items + item, actual_old_size, 0, dir));
+ rassert(
+ pool_alloc(
+ &head,
+ items + item,
+ actual_old_size,
+ mode | POOL_ALLOC_MODE_REALLOC
+ )
+ );
}
else {
base = items[item].base;
}
printf("old region [%d,%d)\n", base, base + actual_old_size);
hash_verify(item, base, actual_old_size - size, 0);
- bool result = pool_realloc(
+ bool result = pool_alloc(
&head,
items + item,
size,
- size - actual_old_size,
- !dir
+ mode ^ (
+ POOL_ALLOC_MODE_LAST_FIT |
+ POOL_ALLOC_MODE_REALLOC
+ )
);
printf(
"... %s\n",
if (!success) {
printf("... undo\n");
rassert(
- pool_realloc(
+ pool_alloc(
&head,
items + item,
actual_old_size,
- actual_old_size - size,
- !dir
+ mode ^ (
+ POOL_ALLOC_MODE_LAST_FIT |
+ POOL_ALLOC_MODE_REALLOC
+ )
)
);
}
#endif
#if !defined(INODE_SWAP) && !defined(PREALLOCATE_SWAP)
rassert(
- pool_realloc(
+ pool_alloc(
&swap_table,
&victim->swap_item,
victim_swap_blocks + blocks,
- 0,
- false
+#ifdef MOVEABLE_SWAP
+ POOL_ALLOC_MODE_MOVEABLE |
+ POOL_ALLOC_MODE_REALLOC
+#else
+ POOL_ALLOC_MODE_REALLOC
+#endif
)
);
#endif
// add to swap pool
victim_swap_blocks = 0;
#if !defined(INODE_SWAP) && !defined(PREALLOCATE_SWAP)
- rassert(pool_alloc(&swap_table, &victim->swap_item, blocks, false));
+ rassert(
+ pool_alloc(
+ &swap_table,
+ &victim->swap_item,
+ blocks,
+#ifdef MOVEABLE_SWAP
+ POOL_ALLOC_MODE_MOVEABLE
+#else
+ 0
+#endif
+ )
+ );
#endif
// remove from LRU list
#ifndef PREALLOCATE_CORE
// no, reduce core allocation
rassert(
- pool_realloc(
+ pool_alloc(
&core_table,
&victim->core_item,
victim_core_blocks,
- -blocks,
- true
+ POOL_ALLOC_MODE_LAST_FIT |
+#ifdef MOVEABLE_CORE
+ POOL_ALLOC_MODE_MOVEABLE |
+#endif
+ POOL_ALLOC_MODE_REALLOC
)
);
#endif
#else
blocks = (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT);
if (
- process_avail < blocks
#if defined(PREALLOCATE_SWAP) && !defined(MOVEABLE_SWAP)
- || !pool_alloc(&swap_table, &process->swap_item, blocks, false)
+ process_avail < blocks ||
+ !pool_alloc(
+ &swap_table,
+ &process->swap_item,
+ blocks,
+ 0
+ )
+#else
+ process_avail < blocks
#endif
)
return false;
// allocate core and possible swap
#ifdef MOVEABLE_CORE
- rassert(pool_alloc(&core_table, &process->core_item, blocks, false));
+ rassert(
+ pool_alloc(
+ &core_table,
+ &process->core_item,
+ blocks,
+ POOL_ALLOC_MODE_MOVEABLE
+ )
+ );
#else
- if (!pool_alloc(&core_table, &process->core_item, blocks, false)) {
+ if (
+ !pool_alloc(
+ &core_table,
+ &process->core_item,
+ blocks,
+ 0
+ )
+ ) {
#ifdef INODE_SWAP
//printf("deref inode %d\n", process->swap_inode->c_num);
i_deref(process->swap_inode);
}
#endif
#if defined(PREALLOCATE_SWAP) && defined(MOVEABLE_SWAP)
- rassert(pool_alloc(&swap_table, &process->swap_item, blocks, false));
+ rassert(
+ pool_alloc(
+ &swap_table,
+ &process->swap_item,
+ blocks,
+ POOL_ALLOC_MODE_MOVEABLE
+ )
+ );
#endif
#ifdef INDIRECT_CORE
#endif
#if defined(PREALLOCATE_SWAP) && !defined(MOVEABLE_SWAP)
+ // this is a bit clunky, we want realloc without copying old contents,
+ // so we free, try to allocate larger, if that fails, allocate original
pool_free(&swap_table, &process->swap_item);
- if (!pool_alloc(&swap_table, &process->swap_item, blocks, false)) {
- rassert(pool_alloc(&swap_table, &process->swap_item, old_blocks, false));
+ if (
+ !pool_alloc(
+ &swap_table,
+ &process->swap_item,
+ blocks,
+ 0
+ )
+ ) {
+ rassert(
+ pool_alloc(
+ &swap_table,
+ &process->swap_item,
+ old_blocks,
+ 0
+ )
+ );
return false;
}
#endif
// reallocate core and possible swap
#ifdef MOVEABLE_CORE
- rassert(pool_realloc(&core_table, &process->core_item, blocks, 0, false));
+ rassert(
+ pool_alloc(
+ &core_table,
+ &process->core_item,
+ blocks,
+ POOL_ALLOC_MODE_MOVEABLE |
+ POOL_ALLOC_MODE_REALLOC
+ )
+ );
#else
- if (!pool_realloc(&core_table, &process->core_item, blocks, 0, false)) {
+ if (
+ !pool_alloc(
+ &core_table,
+ &process->core_item,
+ blocks,
+ POOL_ALLOC_MODE_REALLOC
+ )
+ ) {
#if defined(PREALLOCATE_SWAP) && !defined(MOVEABLE_SWAP)
pool_free(&swap_table, &process->swap_item);
- rassert(pool_alloc(&swap_table, &process->swap_item, old_blocks, false));
+ rassert(
+ pool_alloc(
+ &swap_table,
+ &process->swap_item,
+ old_blocks,
+ 0
+ )
+ );
#endif
return false;
}
#endif
#if defined(PREALLOCATE_SWAP) && defined(MOVEABLE_SWAP)
pool_free(&swap_table, &process->swap_item);
- rassert(pool_alloc(&swap_table, &process->swap_item, blocks, false));
+ rassert(
+ pool_alloc(
+ &swap_table,
+ &process->swap_item,
+ blocks,
+ POOL_ALLOC_MOVEABLE
+ )
+ );
#endif
#ifdef INDIRECT_CORE
// add to core pool
process_core_blocks = 0;
#ifndef PREALLOCATE_CORE
- rassert(pool_alloc(&core_table, &process->core_item, blocks, false));
+ rassert(
+ pool_alloc(
+ &core_table,
+ &process->core_item,
+ blocks,
+#ifdef MOVEABLE_CORE
+ POOL_ALLOC_MODE_MOVEABLE
+#else
+ 0
+#endif
+ )
+ );
#endif
goto loop_entry_full;
}
f_trunc(process->swap_inode);
#else
rassert(
- pool_realloc(
+ pool_alloc(
&swap_table,
&process->swap_item,
process_swap_blocks,
- false
+#ifdef MOVEABLE_SWAP
+ POOL_ALLOC_MODE_MOVEABLE |
+ POOL_ALLOC_MODE_REALLOC
+#else
+ POOL_ALLOC_MODE_REALLOC
+#endif
)
);
#endif
// increase core allocation
#ifndef PREALLOCATE_CORE
rassert(
- pool_realloc(
+ pool_alloc(
&core_table,
&process->core_item,
process_core_blocks + blocks,
- blocks,
- true
+ POOL_ALLOC_MODE_LAST_FIT |
+#ifdef MOVEABLE_CORE
+ POOL_ALLOC_MODE_MOVEABLE |
+#endif
+ POOL_ALLOC_MODE_REALLOC
)
);
#endif
public / moveable_pool.git / commitdiff