From 8623ea05567e7cab9605df9a505c88a215467245 Mon Sep 17 00:00:00 2001 From: Nick Downing Date: Wed, 20 Mar 2019 00:13:23 +1100 Subject: [PATCH] Implement INDIRECT_CORE, fix calculations so that PREALLOCATE_CORE make sense --- core.c | 134 +++++++++++++++++++++++++++-- core.h | 26 +++++- o.sh | 4 +- process.c | 207 ++++++++++++++++++++++++++------------------- process.h | 2 +- process_test_run.c | 96 +++++++++++++++------ swap.c | 79 ++++++++++++----- swap.h | 7 ++ 8 files changed, 416 insertions(+), 139 deletions(-) diff --git a/core.c b/core.c index c415cfd..04a06b5 100644 --- a/core.c +++ b/core.c @@ -5,9 +5,22 @@ #include "rassert.h" struct pool_head core_table; + +#ifdef INDIRECT_CORE +static uint8_t masks[8] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80}; +static uint8_t bits[8] = {1, 2, 4, 8, 0x10, 0x20, 0x40, 0x80}; + +int n_core_blocks; +int n_core_block_bitmap; +uint8_t *core_block_bitmap; +int core_block_next; +int core_block_avail; + +int *core_table_mem; +#endif int *core_block_mem; -void core_move(struct pool_item *item, int new_base) { +static void core_move(struct pool_item *item, int new_base) { int base = item->base; int size = item->limit - base; printf( @@ -17,16 +30,21 @@ void core_move(struct pool_item *item, int new_base) { new_base, new_base + size ); - assert(new_base < base || new_base >= base + size); + assert(new_base <= base || new_base >= base + size); for (int i = 0; i < size; ++i) { +#ifdef INDIRECT_CORE + core_table_mem[new_base + i] = core_table_mem[base + i]; + core_table_mem[base + i] = 0x55555555; +#else core_block_mem[new_base + i] = core_block_mem[base + i]; core_block_mem[base + i] = 0xaaaaaaaa; +#endif } } -void core_move_up(struct pool_item *item, int new_limit) { +#ifdef MOVEABLE_CORE +static void core_move_up(struct pool_item *item, int new_limit) { int limit = item->limit; - assert(limit != new_limit); int neg_size = item->base - limit; printf( "core_move_up [%d,%d) to [%d,%d)\n", @@ -35,23 +53,127 @@ void core_move_up(struct pool_item *item, int new_limit) { new_limit + neg_size, new_limit ); - assert(new_limit > limit || new_limit <= limit + neg_size); + assert(new_limit >= limit || new_limit <= limit + neg_size); for (int i = -1; i >= neg_size; --i) { +#ifdef INDIRECT_CORE + core_table_mem[new_limit + i] = core_table_mem[limit + i]; + core_table_mem[limit + i] = 0x55555555; +#else core_block_mem[new_limit + i] = core_block_mem[limit + i]; core_block_mem[limit + i] = 0xaaaaaaaa; +#endif } } +#endif -void core_init(int table_size, int table_spare) { +#ifdef INDIRECT_CORE +void core_init(int table_size, int table_spare, int n_blocks) +#else +void core_init(int table_size, int table_spare) +#endif +{ pool_init( &core_table, 0, table_size, table_spare, core_move, +#ifdef MOVEABLE_CORE core_move_up +#else + NULL +#endif ); +#ifdef INDIRECT_CORE + n_core_blocks = n_blocks; + n_core_block_bitmap = (n_core_blocks + 7) >> 3; + core_block_bitmap = malloc(n_core_block_bitmap); + rassert(core_block_bitmap); + memset(core_block_bitmap, 0xff, n_core_block_bitmap); + if (n_core_blocks & 7) + core_block_bitmap[n_core_blocks >> 3] = ~masks[n_core_blocks & 7]; + core_block_next = 0; + core_block_avail = n_core_blocks; + + core_table_mem = malloc(table_size * sizeof(int)); + rassert(core_table_mem); + memset(core_table_mem, 0x55, table_size * sizeof(int)); + + core_block_mem = malloc(n_blocks * sizeof(int)); + rassert(core_block_mem); + memset(core_block_mem, 0xaa, n_blocks * sizeof(int)); +#else core_block_mem = malloc(table_size * sizeof(int)); + rassert(core_block_mem); memset(core_block_mem, 0xaa, table_size * sizeof(int)); +#endif +} + +#ifdef INDIRECT_CORE +bool core_block_alloc(int *table, int size) { + int i, j, k; + uint8_t c; + + if (core_block_avail < size) + return false; + + for (i = 0; i < size; ++i) { + j = core_block_next >> 3; + c = core_block_bitmap[j] & masks[core_block_next & 7]; + goto loop_entry; + for (; j < n_core_block_bitmap; ++j) { + c = core_block_bitmap[j]; + loop_entry: + if (c) goto found; + } +#if 1 + for (j = 0; ; ++j) { + assert(j <= core_block_next >> 3); + c = core_block_bitmap[j]; + if (c) goto found; + } +#else + k = (core_block_next >> 3) + 1; + for (j = 0; j < k; ++j) { + c = core_block_bitmap[j]; + if (c) goto found; + } + core_block_free(table, i); + return false; +#endif + + found: + for (k = 0; (c & 1) == 0; ++k) + c >>= 1; + core_block_bitmap[j] &= ~bits[k]; + core_block_next = (j << 3) | k; + + assert(table[i] == 0x55555555); + table[i] = core_block_next++; + if (core_block_next >= n_core_blocks) + core_block_next = 0; + } + + core_block_avail -= size; + return true; +} + +void core_block_free(int *table, int size) { + int i, j, k; + + for (i = 0; i < size; ++i) { + j = table[i]; + assert(j >= 0 && j < n_core_blocks); + k = j & 7; + j >>= 3; + assert((core_block_bitmap[j] & bits[k]) == 0); + core_block_bitmap[j] |= bits[k]; +#ifndef NDEBUG + table[i] = 0x55555555; +#endif + } + + core_block_avail += size; } +#endif diff --git a/core.h b/core.h index a9cb734..71a2fb7 100644 --- a/core.h +++ b/core.h @@ -1,9 +1,11 @@ #ifndef _CORE_H #define _CORE_H 1 +#include #include "pool.h" -#define MOVEABLE_CORE 1 +#define INDIRECT_CORE 1 +//#define MOVEABLE_CORE 1 #ifdef MOVEABLE_CORE #define core_table_alloc(item, size) \ @@ -18,9 +20,31 @@ #endif #define core_table_free(item) pool_free(&core_table, item) +#ifdef INDIRECT_CORE +#define core_avail() core_block_avail +#else +#define core_avail() core_table.avail +#endif + extern struct pool_head core_table; + +#ifdef INDIRECT_CORE +extern int n_core_blocks; +int n_core_block_bitmap; +extern uint8_t *core_block_bitmap; +extern int core_block_next; +extern int core_block_avail; + +extern int *core_table_mem; +#endif extern int *core_block_mem; +#ifdef INDIRECT_CORE +void core_init(int n_table, int table_spare, int n_blocks); +bool core_block_alloc(int *blocks, int size); +void core_block_free(int *blocks, int size); +#else void core_init(int n_table, int table_spare); +#endif #endif diff --git a/o.sh b/o.sh index c1eb979..a7f24bc 100755 --- a/o.sh +++ b/o.sh @@ -12,4 +12,6 @@ echo "run test script" # moveable swap (useable with any configuration): #./process_test_run 16 64 0 192 0 16 + core_table.item.base - + core_table.item.limit - + core_table.spare + ) + avail = + core_table.item.base - + core_table.item.limit - + core_table.spare; +#endif +#if defined(PREALLOCATE_SWAP) + if ( + avail > + swap_table.item.base - + swap_table.item.limit - + swap_table.spare + ) + avail = + swap_table.item.base - + swap_table.item.limit - + swap_table.spare; #endif if (victim == NULL) { #ifdef PREALLOCATE_CORE @@ -182,31 +175,14 @@ void process_init(int n, int spare) { processes[i].size = -1; #endif -#if defined(PREALLOCATE_CORE) && defined(PREALLOCATE_SWAP) -#ifdef INDIRECT_SWAP - int swap_avail = n_swap_blocks; -#else - int swap_avail = swap_table.avail; -#endif - process_avail = ( - core_table.avail < swap_avail ? core_table.avail : swap_avail - ) - spare; -#elif defined(PREALLOCATE_CORE) - process_avail = core_table.avail - spare; -#elif defined(PREALLOCATE_SWAP) -#ifdef INDIRECT_SWAP - int swap_avail = n_swap_blocks; -#else - int swap_avail = swap_table.avail; -#endif - process_avail = swap_avail - spare; -#else -#ifdef INDIRECT_SWAP - int swap_avail = n_swap_blocks; -#else - int swap_avail = swap_table.avail; + process_avail = core_avail() + swap_avail() - spare; +#ifdef PREALLOCATE_CORE + if (process_avail > core_table.avail) + process_avail = core_table.avail; #endif - process_avail = core_table.avail + swap_avail - spare; +#ifdef PREALLOCATE_SWAP + if (process_avail > swap_table.avail) + process_avail = swap_table.avail; #endif process_spare = spare; @@ -304,6 +280,9 @@ static void do_swap_out(int swap_out) { rassert(swap_block_alloc(swap_table_mem + swap_base, size)); #endif swap_write(swap_base, core_base, size); +#ifdef INDIRECT_CORE + core_block_free(core_table_mem + core_base, size); +#endif // see if victim fully swapped out victim_core_size -= size; @@ -356,10 +335,8 @@ bool process_alloc(struct process *process, int size) { return false; // free up as much core as we need to - swap_out = size - core_table.avail; -#ifndef PREALLOCATE_SWAP - assert(swap_out <= swap_table.avail); -#endif + swap_out = size - core_avail(); + assert(swap_out <= swap_avail()); do_swap_out(swap_out); // allocate core and possible swap @@ -395,6 +372,20 @@ bool process_alloc(struct process *process, int size) { rassert(swap_table_alloc(&process->swap_item, size)); #endif +#ifdef INDIRECT_CORE + // populate new table with physical blocks + rassert( + core_block_alloc( +#ifdef PREALLOCATE_CORE + core_table_mem + process->core_item.base, +#else + core_table_mem + process->pool_item.base, +#endif + size + ) + ); +#endif + // insert at head of LRU list process->lru_item.prev = &lru_head; process->lru_item.next = lru_head.next; @@ -430,10 +421,8 @@ bool process_realloc(struct process *process, int size) { #endif // free up as much core as we need to - swap_out = size_change - core_table.avail; -#ifndef PREALLOCATE_SWAP - assert(swap_out <= swap_table.avail); -#endif + swap_out = size_change - core_avail(); + assert(swap_out <= swap_avail()); do_swap_out(swap_out); // reallocate core and possible swap @@ -472,6 +461,32 @@ bool process_realloc(struct process *process, int size) { rassert(swap_table_alloc(&process->swap_item, size)); #endif +#ifdef INDIRECT_CORE + // populate new table with physical blocks or discard them + if (size_change >= 0) + rassert( + core_block_alloc( +#ifdef PREALLOCATE_CORE + core_table_mem + process->core_item.limit - size_change, +#else + core_table_mem + process->pool_item.limit - size_change, +#endif + size_change + ) + ); + else + { + core_block_free( +#ifdef PREALLOCATE_CORE + core_table_mem + process->core_item.limit, +#else + core_table_mem + process->pool_item.limit, +#endif + -size_change + ); + } +#endif + // track total allocation process->size = size; process_avail -= size_change; @@ -524,16 +539,14 @@ void process_run(struct process *process) { // calculate amount to swap size = process_swap_size; - swap_out = size - core_table.avail; - if (swap_out > swap_table.avail) { - size += swap_table.avail - swap_out; - swap_out = swap_table.avail; + swap_out = size - core_avail(); + if (swap_out > swap_avail()) { + size += swap_avail() - swap_out; + swap_out = swap_avail(); } // free up as much core as we can -#ifndef PREALLOCATE_SWAP - assert(swap_out <= swap_table.avail); -#endif + assert(swap_out <= swap_avail()); do_swap_out(swap_out); // add to core pool, using dedicated core item @@ -576,10 +589,10 @@ void process_run(struct process *process) { #endif // calculate how much to swap size = process_swap_size; - swap_out = size - core_table.avail; - if (swap_out > swap_table.avail) { - size += swap_table.avail - swap_out; - swap_out = swap_table.avail; + swap_out = size - core_avail(); + if (swap_out > swap_avail()) { + size += swap_avail() - swap_out; + swap_out = swap_avail(); } // free up as much core as we can @@ -602,6 +615,9 @@ void process_run(struct process *process) { core_base = process->core_item.base + process_core_size - size; #else core_base = process_core_item.limit - size; +#endif +#ifdef INDIRECT_CORE + core_block_alloc(core_table_mem + core_base, size); #endif swap_read(swap_base, core_base, size); #ifdef INDIRECT_SWAP @@ -642,7 +658,20 @@ void process_free(struct process *process) { process->lru_item.prev->next = process->lru_item.next; process->lru_item.next->prev = process->lru_item.prev; -#ifndef PREALLOCATE_CORE +#ifdef PREALLOCATE_CORE +#ifdef INDIRECT_SWAP + core_block_free( + core_table_mem + process->core_item.base, + process->core_item.limit - process->core_item.base + ); +#endif +#else +#ifdef INDIRECT_SWAP + core_block_free( + core_table_mem + process->pool_item.base, + process->pool_item.limit - process->pool_item.base + ); +#endif core_table_free(&process->pool_item); #endif } @@ -650,13 +679,24 @@ void process_free(struct process *process) { // victim, free the dedicated pool items victim = NULL; #ifdef PREALLOCATE_CORE +#ifdef INDIRECT_CORE + core_block_free( + core_table_mem + process->core_item.base, + victim_core_size + ); +#endif victim_core_size = 0; #else +#ifdef INDIRECT_CORE + core_block_free( + core_table_mem + victim_core_item.base, + victim_core_item.limit - victim_core_item.base + ); +#endif core_table_free(&victim_core_item); #endif #ifdef PREALLOCATE_SWAP #ifdef INDIRECT_SWAP - printf("free 1\n"); swap_block_free( swap_table_mem + ~(process->swap_item.base + victim_swap_size), victim_swap_size @@ -665,7 +705,6 @@ void process_free(struct process *process) { victim_swap_size = 0; #else #ifdef INDIRECT_SWAP - printf("free 2\n"); swap_block_free( swap_table_mem + ~victim_swap_item.limit, victim_swap_item.limit - victim_swap_item.base @@ -678,7 +717,6 @@ void process_free(struct process *process) { // fully in swap, remove from swap pool #ifdef PREALLOCATE_SWAP #ifdef INDIRECT_SWAP - printf("free 3\n"); swap_block_free( swap_table_mem + ~(process->swap_item.limit), process->swap_item.limit - process->swap_item.base @@ -686,7 +724,6 @@ void process_free(struct process *process) { #endif #else #ifdef INDIRECT_SWAP - printf("free 4\n"); swap_block_free( swap_table_mem + ~(process->pool_item.limit), process->pool_item.limit - process->pool_item.base diff --git a/process.h b/process.h index cc9e735..f24fc14 100644 --- a/process.h +++ b/process.h @@ -3,7 +3,7 @@ #include "pool.h" -//#define PREALLOCATE_CORE 1 +#define PREALLOCATE_CORE 1 #define PREALLOCATE_SWAP 1 struct lru_item { diff --git a/process_test_run.c b/process_test_run.c index 2498535..c631c46 100644 --- a/process_test_run.c +++ b/process_test_run.c @@ -9,7 +9,11 @@ int main(int argc, char **argv) { if (argc < 7) { -#ifdef INDIRECT_SWAP +#if defined(INDIRECT_CORE) && defined(INDIRECT_SWAP) + printf("usage: %s n_processes core_table_size core_table_spare swap_table_size swap_table_spare spare [n_core_blocks [n_swap_blocks]]\n", argv[0]); +#elif defined(INDIRECT_CORE) + printf("usage: %s n_processes core_table_size core_table_spare swap_table_size swap_table_spare spare [n_core_blocks]\n", argv[0]); +#elif defined(INDIRECT_SWAP) printf("usage: %s n_processes core_table_size core_table_spare swap_table_size swap_table_spare spare [n_swap_blocks]\n", argv[0]); #else printf("usage: %s n_processes core_table_size core_table_spare swap_table_size swap_table_spare spare\n", argv[0]); @@ -22,11 +26,20 @@ int main(int argc, char **argv) { int swap_table_size = atoi(argv[4]); int swap_table_spare = atoi(argv[5]); int spare = atoi(argv[6]); -#ifdef INDIRECT_SWAP +#if defined(INDIRECT_CORE) && defined(INDIRECT_SWAP) + int n_core_blocks = argc >= 8 ? atoi(argv[7]) : core_table_size; + int n_swap_blocks = argc >= 9 ? atoi(argv[8]) : swap_table_size; +#elif defined(INDIRECT_CORE) + int n_core_blocks = argc >= 8 ? atoi(argv[7]) : core_table_size; +#elif defined(INDIRECT_SWAP) int n_swap_blocks = argc >= 8 ? atoi(argv[7]) : swap_table_size; #endif +#ifdef INDIRECT_CORE + core_init(core_table_size, core_table_spare, n_core_blocks); +#else core_init(core_table_size, core_table_spare); +#endif #ifdef INDIRECT_SWAP swap_init(swap_table_size, swap_table_spare, n_swap_blocks); #else @@ -37,7 +50,7 @@ int main(int argc, char **argv) { processes[i].size = -1; while (true) { - //printf("avail %d %d %d\n", process_avail, core_table.avail, swap_table.avail); + printf("avail %d %d(%d) %d(%d)\n", process_avail, core_avail(), core_table.avail, swap_avail(), swap_table.avail); char buf[256]; switch (scanf("%s", buf)) { case -1: @@ -81,8 +94,14 @@ int main(int argc, char **argv) { long long hash = process * 17 + i * 29; hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); - rassert(core_block_mem[core_base + i] == 0xaaaaaaaa); - core_block_mem[core_base + i] = (int)hash; +#ifdef INDIRECT_CORE + int core_block = core_table_mem[core_base + i]; +#else + int core_block = core_base + i; +#endif + printf("%d\n", core_block); + rassert(core_block_mem[core_block] == 0xaaaaaaaa); + core_block_mem[core_block] = (int)hash; } #ifdef PREALLOCATE_SWAP printf("new swap [%d,%d)\n", ~processes[process].swap_item.limit, ~processes[process].swap_item.base); @@ -107,15 +126,28 @@ int main(int argc, char **argv) { ); else { #ifdef PREALLOCATE_CORE - printf("old core [%d,%d)\n", processes[process].core_item.base, processes[process].core_item.limit); + int core_base = processes[process].core_item.base; #else - printf("old core [%d,%d)\n", processes[process].pool_item.base, processes[process].pool_item.limit); -#endif -#ifdef PREALLOCATE_SWAP - printf("old swap [%d,%d)\n", ~processes[process].swap_item.limit, processes[process].swap_item.base); + int core_base = processes[process].pool_item.base; #endif int actual_old_size = processes[process].size; rassert(actual_old_size <= old_size); + printf("old core [%d,%d)\n", core_base, core_base + actual_old_size); +#ifdef PREALLOCATE_SWAP + printf("old swap [%d,%d)\n", ~processes[process].swap_item.limit, ~processes[process].swap_item.base); +#endif + for (int i = size; i < actual_old_size; ++i) { + long long hash = process * 17 + i * 29; + hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); + hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); +#ifdef INDIRECT_CORE + int core_block = core_table_mem[core_base + i]; +#else + int core_block = core_base + i; +#endif + rassert(core_block_mem[core_block] == (int)hash); + core_block_mem[core_block] = 0xaaaaaaaa; + } bool result = process_realloc(processes + process, size); printf( "realloc %d %d(%d) %d %d: %s\n", @@ -135,24 +167,22 @@ int main(int argc, char **argv) { } else { #ifdef PREALLOCATE_CORE - int core_base = processes[process].core_item.base; + core_base = processes[process].core_item.base; #else - int core_base = processes[process].pool_item.base; + core_base = processes[process].pool_item.base; #endif printf("new core [%d,%d)\n", core_base, core_base + size); for (int i = actual_old_size; i < size; ++i) { long long hash = process * 17 + i * 29; hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); - rassert(core_block_mem[core_base + i] == 0xaaaaaaaa); - core_block_mem[core_base + i] = (int)hash; - } - for (int i = size; i < actual_old_size; ++i) { - long long hash = process * 17 + i * 29; - hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); - hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); - rassert(core_block_mem[core_base + i] == (int)hash); - core_block_mem[core_base + i] = 0xaaaaaaaa; +#ifdef INDIRECT_CORE + int core_block = core_table_mem[core_base + i]; +#else + int core_block = core_base + i; +#endif + rassert(core_block_mem[core_block] == 0xaaaaaaaa); + core_block_mem[core_block] = (int)hash; } #ifdef PREALLOCATE_SWAP printf("new swap [%d,%d)\n", ~processes[process].swap_item.limit, ~processes[process].swap_item.base); @@ -210,8 +240,13 @@ int main(int argc, char **argv) { hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); if (i < core_size) { - rassert(core_block_mem[core_base + i] == (int)hash); - core_block_mem[core_base + i] = 0xaaaaaaaa; +#ifdef INDIRECT_CORE + int core_block = core_table_mem[core_base + i]; +#else + int core_block = core_base + i; +#endif + rassert(core_block_mem[core_block] == (int)hash); + core_block_mem[core_block] = 0xaaaaaaaa; } else { #ifdef INDIRECT_SWAP @@ -266,12 +301,19 @@ done: hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); hash = (hash & 0xffffffffffffffffLL) + (hash >> 32); if (j < core_size) { - rassert(core_block_mem[core_base + j] == (int)hash); - core_block_mem[core_base + j] = 0xaaaaaaaa; +#ifdef INDIRECT_CORE + int core_block = core_table_mem[core_base + j]; + core_table_mem[core_base + j] = 0x55555555; +#else + int core_block = core_base + j; +#endif + rassert(core_block_mem[core_block] == (int)hash); + core_block_mem[core_block] = 0xaaaaaaaa; } else { #ifdef INDIRECT_SWAP int swap_block = swap_table_mem[swap_base + j - core_size]; + swap_table_mem[swap_base + j - core_size] = 0x55555555; #else int swap_block = swap_base + j - core_size; #endif @@ -283,6 +325,10 @@ done: } for (int i = 0; i < core_table.item.base; ++i) +#ifdef INDIRECT_CORE + rassert(core_table_mem[i] == 0x55555555); + for (int i = 0; i < n_core_blocks; ++i) +#endif rassert(core_block_mem[i] == 0xaaaaaaaa); int swap_limit = ~swap_table.item.base; for (int i = 0; i < swap_limit; ++i) diff --git a/swap.c b/swap.c index e94b397..574385d 100644 --- a/swap.c +++ b/swap.c @@ -15,12 +15,12 @@ int n_swap_blocks; int n_swap_block_bitmap; uint8_t *swap_block_bitmap; int swap_block_next; +int swap_block_avail; int *swap_table_mem; #endif int *swap_block_mem; -#ifdef MOVEABLE_SWAP // swap address native wrt. pool and complemented wrt. backing store, // means that swap_move() moves upward in backing store, do backward static void swap_move(struct pool_item *item, int new_base) { @@ -38,11 +38,17 @@ static void swap_move(struct pool_item *item, int new_base) { ); assert(new_limit >= limit || new_limit <= limit + neg_size); for (int i = -1; i >= neg_size; --i) { +#ifdef INDIRECT_SWAP swap_table_mem[new_limit + i] = swap_table_mem[limit + i]; - swap_table_mem[limit + i] = 0xaaaaaaaa; + swap_table_mem[limit + i] = 0x55555555; +#else + swap_block_mem[new_limit + i] = swap_block_mem[limit + i]; + swap_block_mem[limit + i] = 0xaaaaaaaa; +#endif } } +#ifdef MOVEABLE_SWAP // swap address native wrt. pool and complemented wrt. backing store, // means that swap_move_up() moves downward in backing store, do forward static void swap_move_up(struct pool_item *item, int new_limit) { @@ -60,8 +66,13 @@ static void swap_move_up(struct pool_item *item, int new_limit) { ); assert(new_base <= base || new_base >= base + size); for (int i = 0; i < size; ++i) { +#ifdef INDIRECT_SWAP swap_table_mem[new_base + i] = swap_table_mem[base + i]; - swap_table_mem[base + i] = 0xaaaaaaaa; + swap_table_mem[base + i] = 0x55555555; +#else + swap_block_mem[new_base + i] = swap_block_mem[base + i]; + swap_block_mem[base + i] = 0xaaaaaaaa; +#endif } } #endif @@ -77,11 +88,10 @@ void swap_init(int table_size, int table_spare) ~table_size, -1, table_spare, -#ifdef MOVEABLE_SWAP swap_move, +#ifdef MOVEABLE_SWAP swap_move_up #else - NULL, NULL #endif ); @@ -92,20 +102,23 @@ void swap_init(int table_size, int table_spare) swap_block_bitmap = malloc(n_swap_block_bitmap); rassert(swap_block_bitmap); memset(swap_block_bitmap, 0xff, n_swap_block_bitmap); - if (n_blocks & 7) + if (n_swap_blocks & 7) swap_block_bitmap[n_swap_blocks >> 3] = ~masks[n_swap_blocks & 7]; swap_block_next = 0; + swap_block_avail = n_swap_blocks; swap_table_mem = malloc(table_size * sizeof(int)); rassert(swap_table_mem); memset(swap_table_mem, 0x55, table_size * sizeof(int)); swap_block_mem = malloc(n_blocks * sizeof(int)); + rassert(swap_block_mem); + memset(swap_block_mem, 0xaa, n_blocks * sizeof(int)); #else swap_block_mem = malloc(table_size * sizeof(int)); -#endif rassert(swap_block_mem); - memset(swap_block_mem, 0xaa, n_blocks * sizeof(int)); + memset(swap_block_mem, 0xaa, table_size * sizeof(int)); +#endif } #ifdef INDIRECT_SWAP @@ -113,36 +126,48 @@ bool swap_block_alloc(int *table, int size) { int i, j, k; uint8_t c; + if (swap_block_avail < size) + return false; + for (i = 0; i < size; ++i) { j = swap_block_next >> 3; - c = swap_block_bitmap[j] & masks[j & 7]; + c = swap_block_bitmap[j] & masks[swap_block_next & 7]; goto loop_entry; for (; j < n_swap_block_bitmap; ++j) { c = swap_block_bitmap[j]; loop_entry: if (c) goto found; } +#if 1 + for (j = 0; ; ++j) { + assert(j <= swap_block_next >> 3); + c = swap_block_bitmap[j]; + if (c) goto found; + } +#else k = (swap_block_next >> 3) + 1; for (j = 0; j < k; ++j) { c = swap_block_bitmap[j]; if (c) goto found; } - swap_block_free(table, i); return false; +#endif found: for (k = 0; (c & 1) == 0; ++k) c >>= 1; swap_block_bitmap[j] &= ~bits[k]; assert(table[i] == 0x55555555); - j = (j << 3) | k; - table[i] = j++; - if (j >= n_swap_blocks) - j = 0; - swap_block_next = j; + swap_block_next = (j << 3) | k; + + assert(table[i] == 0x55555555); + table[i] = swap_block_next++; + if (swap_block_next >= n_swap_blocks) + swap_block_next = 0; } + swap_block_avail -= size; return true; } @@ -160,6 +185,8 @@ void swap_block_free(int *table, int size) { table[i] = 0x55555555; #endif } + + swap_block_avail += size; } #endif @@ -176,8 +203,14 @@ void swap_read(int swap_base, int core_base, int size) { #else int swap_block = swap_base + i; #endif - assert(core_block_mem[core_base + i] == 0xaaaaaaaa); - core_block_mem[core_base + i] = swap_block_mem[swap_block]; +#ifdef INDIRECT_CORE + int core_block = core_table_mem[core_base + i]; + printf(",%d", core_block); +#else + int core_block = core_base + i; +#endif + assert(core_block_mem[core_block] == 0xaaaaaaaa); + core_block_mem[core_block] = swap_block_mem[swap_block]; swap_block_mem[swap_block] = 0xaaaaaaaa; } #ifdef INDIRECT_SWAP @@ -192,15 +225,21 @@ void swap_write(int swap_base, int core_base, int size) { printf("blocks"); #endif for (int i = 0; i < size; ++i) { +#ifdef INDIRECT_CORE + int core_block = core_table_mem[core_base + i]; + printf(" %d", core_block); +#else + int core_block = core_base + i; +#endif #ifdef INDIRECT_SWAP int swap_block = swap_table_mem[swap_base + i]; - printf(" %d", swap_block); + printf(",%d", swap_block); #else int swap_block = swap_base + i; #endif assert(swap_block_mem[swap_block] == 0xaaaaaaaa); - swap_block_mem[swap_block] = core_block_mem[core_base + i]; - core_block_mem[core_base + i] = 0xaaaaaaaa; + swap_block_mem[swap_block] = core_block_mem[core_block]; + core_block_mem[core_block] = 0xaaaaaaaa; } #ifdef INDIRECT_SWAP printf("\n"); diff --git a/swap.h b/swap.h index 6d17e37..4944851 100644 --- a/swap.h +++ b/swap.h @@ -20,6 +20,12 @@ #endif #define swap_table_free(item) pool_free(&swap_table, item) +#ifdef INDIRECT_SWAP +#define swap_avail() swap_block_avail +#else +#define swap_avail() swap_table.avail +#endif + extern struct pool_head swap_table; #ifdef INDIRECT_SWAP @@ -27,6 +33,7 @@ extern int n_swap_blocks; int n_swap_block_bitmap; extern uint8_t *swap_block_bitmap; extern int swap_block_next; +extern int swap_block_avail; extern int *swap_table_mem; #endif -- 2.34.1