Implement INDIRECT_CORE, fix calculations so that PREALLOCATE_CORE make sense

diff --git a/core.c b/core.c
index c415cfd..04a06b5 100644 (file)
--- 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 (file)
--- a/core.h
+++ b/core.h
@@ -1,9 +1,11 @@
 #ifndef _CORE_H
 #define _CORE_H 1
 
+#include <stdint.h>
 #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 (executable)
--- 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 <process_test.txt
 # non moveable swap (must be preallocated, may be indirect):
-./process_test_run 16 64 0 384 0 16 192 <process_test.txt
+#./process_test_run 16 64 0 384 0 16 192 <process_test.txt
+# non moveable core and swap (must be preallocated, may be indirect):
+./process_test_run 16 384 0 384 0 16 64 192 <process_test.txt

diff --git a/process.c b/process.c
index d75fbec..b2f6985 100644 (file)
--- a/process.c
+++ b/process.c
@@ -30,52 +30,45 @@ struct pool_item victim_swap_item;
 #if 1
 // won't work when compiled with NDEBUG
 static void check_invariants() {
-#if defined(PREALLOCATE_CORE) && defined(PREALLOCATE_SWAP)
-  int core_avail =
-    core_table.item.base -
-    core_table.item.limit -
-    core_table.spare;
-#ifdef INDIRECT_SWAP
-  int swap_avail = n_swap_blocks;
+  int avail =
+#ifdef INDIRECT_CORE
+    n_core_blocks +
 #else
-  int swap_avail =
-    swap_table.item.base -
-    swap_table.item.limit -
-    swap_table.spare;
-#endif
-  int avail = (
-    core_avail < swap_avail ? core_avail : swap_avail
-  ) - process_spare;
-#elif defined(PREALLOCATE_CORE)
-  int core_avail =
     core_table.item.base -
     core_table.item.limit -
-    core_table.spare;
-  int avail = core_avail - process_spare;
-#elif defined(PREALLOCATE_SWAP)
-#ifdef INDIRECT_SWAP
-  int swap_avail = n_swap_blocks;
-#else
-  int swap_avail =
-    swap_table.item.base -
-    swap_table.item.limit -
-    swap_table.spare;
+    core_table.spare +
 #endif
-  int avail = swap_avail - process_spare;
-#else
-  int core_avail =
-    core_table.item.base -
-    core_table.item.limit -
-    core_table.spare;
 #ifdef INDIRECT_SWAP
-  int swap_avail = n_swap_blocks;
+    n_swap_blocks -
 #else
-  int swap_avail =
     swap_table.item.base -
     swap_table.item.limit -
-    swap_table.spare;
+    swap_table.spare -
 #endif
-  int avail = core_avail + swap_avail - process_spare;
+    process_spare;
+#if defined(PREALLOCATE_CORE)
+  if (
+    avail >
+      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 (file)
--- 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 (file)
--- 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 (file)
--- 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 (file)
--- 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