Add INDIRECT_SWAP option

diff --git a/o.sh b/o.sh
index 9555aed..c1eb979 100755 (executable)
--- a/o.sh
+++ b/o.sh
@@ -1,12 +1,15 @@
 #!/bin/sh
 
 echo "generate test script"
-# preallocated core, possible preallocated swap:
+# preallocated core, possible preallocated swap (not indirect):
 #./process_test_gen 16 48 65536 32 >process_test.txt
-# non preallocated core, preallocated swap:
+# non preallocated core, preallocated swap (not indirect):
 #./process_test_gen 16 176 65536 32 >process_test.txt
-# non preallocated core, non preallocated swap:
+# non preallocated core, non preallocated swap (or indirect swap):
 ./process_test_gen 16 240 65536 32 >process_test.txt
 
 echo "run test script"
-./process_test_run 16 64 0 192 0 16 <process_test.txt
+# 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

diff --git a/process.c b/process.c
index 084927b..d75fbec 100644 (file)
--- a/process.c
+++ b/process.c
@@ -31,39 +31,51 @@ struct pool_item victim_swap_item;
 // won't work when compiled with NDEBUG
 static void check_invariants() {
 #if defined(PREALLOCATE_CORE) && defined(PREALLOCATE_SWAP)
-  int core_table_avail =
+  int core_avail =
     core_table.item.base -
     core_table.item.limit -
     core_table.spare;
-  int swap_table_avail =
+#ifdef INDIRECT_SWAP
+  int swap_avail = n_swap_blocks;
+#else
+  int swap_avail =
     swap_table.item.base -
     swap_table.item.limit -
     swap_table.spare;
+#endif
   int avail = (
-    core_table_avail < swap_table_avail ? core_table_avail : swap_table_avail
+    core_avail < swap_avail ? core_avail : swap_avail
   ) - process_spare;
 #elif defined(PREALLOCATE_CORE)
-  int core_table_avail =
+  int core_avail =
     core_table.item.base -
     core_table.item.limit -
     core_table.spare;
-  int avail = core_table_avail - process_spare;
+  int avail = core_avail - process_spare;
 #elif defined(PREALLOCATE_SWAP)
-  int swap_table_avail =
+#ifdef INDIRECT_SWAP
+  int swap_avail = n_swap_blocks;
+#else
+  int swap_avail =
     swap_table.item.base -
     swap_table.item.limit -
     swap_table.spare;
-  int avail = swap_table_avail - process_spare;
+#endif
+  int avail = swap_avail - process_spare;
 #else
-  int core_table_avail =
+  int core_avail =
     core_table.item.base -
     core_table.item.limit -
     core_table.spare;
-  int swap_table_avail =
+#ifdef INDIRECT_SWAP
+  int swap_avail = n_swap_blocks;
+#else
+  int swap_avail =
     swap_table.item.base -
     swap_table.item.limit -
     swap_table.spare;
-  int avail = core_table_avail + swap_table_avail - process_spare;
+#endif
+  int avail = core_avail + swap_avail - process_spare;
 #endif
   if (victim == NULL) {
 #ifdef PREALLOCATE_CORE
@@ -171,15 +183,30 @@ void process_init(int n, int spare) {
 #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_table.avail ? core_table.avail : swap_table.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)
-  process_avail = swap_table.avail - spare;
+#ifdef INDIRECT_SWAP
+  int swap_avail = n_swap_blocks;
 #else
-  process_avail = core_table.avail + swap_table.avail - spare;
+  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;
+#endif
+  process_avail = core_table.avail + swap_avail - spare;
 #endif
   process_spare = spare;
 
@@ -209,7 +236,7 @@ static void do_swap_out(int swap_out) {
 #ifndef PREALLOCATE_SWAP
   int victim_swap_size;
 #endif
-  int size;
+  int size, swap_base, core_base;
 
   // loop entry code for the case of an existing victim
   if (swap_out > 0) {
@@ -263,19 +290,20 @@ static void do_swap_out(int swap_out) {
 
     loop_entry:
       // transfer data to swap
-      swap_write(
 #ifdef PREALLOCATE_SWAP
-        ~(victim->swap_item.base + victim_swap_size),
+      swap_base = ~(victim->swap_item.base + victim_swap_size);
 #else
-        ~victim_swap_item.limit,
+      swap_base = ~victim_swap_item.limit;
 #endif
 #ifdef PREALLOCATE_CORE
-        victim->core_item.base + victim_core_size - size,
+      core_base = victim->core_item.base + victim_core_size - size;
 #else
-        victim_core_item.limit - size,
+      core_base = victim_core_item.limit - size;
 #endif
-        size
-      );
+#ifdef INDIRECT_SWAP
+      rassert(swap_block_alloc(swap_table_mem + swap_base, size));
+#endif
+      swap_write(swap_base, core_base, size);
 
       // see if victim fully swapped out
       victim_core_size -= size;
@@ -326,7 +354,6 @@ bool process_alloc(struct process *process, int size) {
 #endif
   )
     return false;
- printf("%d %d %d\n", process_avail, core_table.avail, swap_table.avail);
 
   // free up as much core as we need to
   swap_out = size - core_table.avail;
@@ -462,6 +489,7 @@ void process_run(struct process *process) {
 #ifndef PREALLOCATE_SWAP
   struct pool_item process_swap_item;
 #endif
+  int swap_base, core_base;
 
   // must be already allocated
   assert(process->size != -1);
@@ -565,19 +593,20 @@ void process_run(struct process *process) {
 
     loop_entry_full:
       // transfer data to core
-      swap_read(
 #ifdef PREALLOCATE_SWAP
-        ~(process->swap_item.base + process_swap_size),
+      swap_base = ~(process->swap_item.base + process_swap_size);
 #else
-        ~process_swap_item.limit,
+      swap_base = ~process_swap_item.limit;
 #endif
 #ifdef PREALLOCATE_CORE
-        process->core_item.base + process_core_size - size,
+      core_base = process->core_item.base + process_core_size - size;
 #else
-        process_core_item.limit - size,
+      core_base = process_core_item.limit - size;
+#endif
+      swap_read(swap_base, core_base, size);
+#ifdef INDIRECT_SWAP
+      swap_block_free(swap_table_mem + swap_base, size);
 #endif
-        size
-      );
 
       process_swap_size -= size;
     } while (process_swap_size);
@@ -605,13 +634,6 @@ void process_free(struct process *process) {
   // must be already allocated
   assert(process->size != -1);
 
-#ifdef PREALLOCATE_CORE
-  core_table_free(&process->core_item);
-#endif
-#ifdef PREALLOCATE_SWAP
-  swap_table_free(&process->swap_item);
-#endif
-
   // see whether fully in core, victim, or fully in swap
   if (process->lru_item.prev != NULL) {
     // fully in core, remove from LRU list and core pool
@@ -633,17 +655,55 @@ void process_free(struct process *process) {
     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
+    );
+#endif
     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
+    );
+#endif
     swap_table_free(&victim_swap_item);
 #endif
   }
-#ifndef PREALLOCATE_SWAP
-  else
+  else {
     // 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 
+    );
+#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 
+    );
+#endif
     swap_table_free(&process->pool_item);
 #endif
+  }
 
+  // free the per-process table entries
+#ifdef PREALLOCATE_CORE
+  core_table_free(&process->core_item);
+#endif
+#ifdef PREALLOCATE_SWAP
+  swap_table_free(&process->swap_item);
+#endif
+ 
   // track total allocation
   process_avail += process->size;
 #ifndef NDEBUG

diff --git a/process.h b/process.h
index 7893db3..cc9e735 100644 (file)
--- a/process.h
+++ b/process.h
@@ -4,7 +4,7 @@
 #include "pool.h"
 
 //#define PREALLOCATE_CORE 1
-//#define PREALLOCATE_SWAP 1
+#define PREALLOCATE_SWAP 1
 
 struct lru_item {
   struct lru_item *prev;

diff --git a/process_test_run.c b/process_test_run.c
index 0ebe636..a62a7b4 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
+    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]);
+#endif
     exit(EXIT_FAILURE);
   }
   int n_processes = atoi(argv[1]);
@@ -18,9 +22,16 @@ 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
+  int n_swap_blocks = argc >= 8 ? atoi(argv[7]) : swap_table_size;
+#endif
 
   core_init(core_table_size, core_table_spare);
+#ifdef INDIRECT_SWAP
+  swap_init(swap_table_size, swap_table_spare, n_swap_blocks);
+#else
   swap_init(swap_table_size, swap_table_spare);
+#endif
   process_init(n_processes, spare);
   for (int i = 0; i < n_processes; ++i)
     processes[i].size = -1;
@@ -67,10 +78,10 @@ int main(int argc, char **argv) {
 #endif
  printf("new core [%d,%d)\n", core_base, core_base + size);
           for (int i = 0; i < size; ++i) {
-            rassert(core_table_mem[core_base + i] == 0xaaaaaaaa);
             long long hash = process * 17 + i * 29;
             hash = (hash & 0xffffffffffffffffLL) + (hash >> 32);
             hash = (hash & 0xffffffffffffffffLL) + (hash >> 32);
+            rassert(core_table_mem[core_base + i] == 0xaaaaaaaa);
             core_table_mem[core_base + i] = (int)hash;
           }
 #ifdef PREALLOCATE_SWAP
@@ -130,10 +141,10 @@ int main(int argc, char **argv) {
 #endif
  printf("new core [%d,%d)\n", core_base, core_base + size);
             for (int i = actual_old_size; i < size; ++i) {
-              rassert(core_table_mem[core_base + i] == 0xaaaaaaaa);
               long long hash = process * 17 + i * 29;
               hash = (hash & 0xffffffffffffffffLL) + (hash >> 32);
               hash = (hash & 0xffffffffffffffffLL) + (hash >> 32);
+              rassert(core_table_mem[core_base + i] == 0xaaaaaaaa);
               core_table_mem[core_base + i] = (int)hash;
             }
             for (int i = size; i < actual_old_size; ++i) {
@@ -192,14 +203,6 @@ int main(int argc, char **argv) {
         int swap_size = is_victim ? swap_limit - victim_swap_item.base : !in_core ? swap_limit - processes[process].pool_item.base : 0;
 #endif
         rassert(core_size + swap_size == actual_old_size);
-        process_free(processes + process);
-        processes[process].size = -1;
-        printf(
-          "free %d %d(%d): ok\n",
-          process,
-          old_size,
-          actual_old_size
-        );
         int swap_base = ~swap_limit;
  printf("old core [%d,%d) swap [%d,%d)\n", core_base, core_base + core_size, swap_base, swap_base + swap_size);
         for (int i = 0; i < actual_old_size; ++i) {
@@ -211,10 +214,24 @@ int main(int argc, char **argv) {
             core_table_mem[core_base + i] = 0xaaaaaaaa;
           }
           else {
+#ifdef INDIRECT_SWAP
+            int block = swap_table_mem[swap_base + i - core_size];
+            rassert(swap_block_mem[block] == (int)hash);
+            swap_block_mem[block] = 0x55555555;
+#else
             rassert(swap_table_mem[swap_base + i - core_size] == (int)hash);
             swap_table_mem[swap_base + i - core_size] = 0xaaaaaaaa;
+#endif
           }
         }
+        process_free(processes + process);
+        processes[process].size = -1;
+        printf(
+          "free %d %d(%d): ok\n",
+          process,
+          old_size,
+          actual_old_size
+        );
       }
     }
     else
@@ -254,8 +271,14 @@ done:
           core_table_mem[core_base + j] = 0xaaaaaaaa;
         }
         else {
+#ifdef INDIRECT_SWAP
+          int block = swap_table_mem[swap_base + j - core_size];
+          rassert(swap_block_mem[block] == (int)hash);
+          swap_block_mem[block] = 0x55555555;
+#else
           rassert(swap_table_mem[swap_base + j - core_size] == (int)hash);
           swap_table_mem[swap_base + j - core_size] = 0xaaaaaaaa;
+#endif
         }
       }
     }
@@ -265,6 +288,10 @@ done:
     rassert(core_table_mem[i] == 0xaaaaaaaa);
   for (int i = 0; i < swap_table.item.base; ++i)
     rassert(swap_table_mem[i] == 0xaaaaaaaa);
+#ifdef INDIRECT_SWAP
+  for (int i = 0; i < n_swap_blocks; ++i)
+    rassert(swap_block_mem[i] == 0x55555555);
+#endif
 
   return 0;
 }

diff --git a/swap.c b/swap.c
index 88efea5..68bca1b 100644 (file)
--- a/swap.c
+++ b/swap.c
@@ -5,6 +5,18 @@
 #include "swap.h"
 #include "rassert.h"
 
+#ifdef INDIRECT_SWAP
+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};
+
+uint8_t *swap_block_bitmap;
+int n_swap_block_bitmap;
+int swap_block_next;
+
+int *swap_block_mem;
+int n_swap_blocks;
+#endif
+
 struct pool_head swap_table;
 int *swap_table_mem;
 
@@ -53,7 +65,12 @@ static void swap_move_up(struct pool_item *item, int new_limit) {
   }
 }
 
-void swap_init(int table_size, int table_spare) {
+#ifdef INDIRECT_SWAP
+void swap_init(int table_size, int table_spare, int n_blocks)
+#else
+void swap_init(int table_size, int table_spare)
+#endif
+{
   pool_init(
     &swap_table,
     ~table_size,
@@ -64,25 +81,125 @@ void swap_init(int table_size, int table_spare) {
   );
 
   swap_table_mem = malloc(table_size * sizeof(int));
+  rassert(swap_table_mem);
   memset(swap_table_mem, 0xaa, table_size * sizeof(int));
+
+#ifdef INDIRECT_SWAP
+  n_swap_block_bitmap = (n_blocks + 7) >> 3;
+  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)
+    swap_block_bitmap[n_blocks >> 3] = ~masks[n_blocks & 7];
+  swap_block_next = 0;
+
+  swap_block_mem = malloc(n_blocks * sizeof(int));
+  rassert(swap_block_mem);
+  memset(swap_block_mem, 0x55, n_blocks * sizeof(int));
+  n_swap_blocks = n_blocks;
+#endif
+}
+
+#ifdef INDIRECT_SWAP
+bool swap_block_alloc(int *blocks, int size) {
+  int i, j, k;
+  uint8_t c;
+
+  for (i = 0; i < size; ++i) {
+    j = swap_block_next >> 3;
+    c = swap_block_bitmap[j] & masks[j & 7];
+    goto loop_entry;
+    for (; j < n_swap_block_bitmap; ++j) {
+      c = swap_block_bitmap[j];
+    loop_entry:
+      if (c) goto found;
+    }
+    k = (swap_block_next >> 3) + 1;
+    for (j = 0; j < k; ++j) {
+      c = swap_block_bitmap[j];
+      if (c) goto found;
+    }
+
+    swap_block_free(blocks, i);
+    return false;
+
+  found:
+    for (k = 0; (c & 1) == 0; ++k)
+      c >>= 1;
+    swap_block_bitmap[j] &= ~bits[k];
+    assert(blocks[i] == 0xaaaaaaaa);
+    j = (j << 3) | k;
+    blocks[i] = j++;
+    if (j >= n_swap_blocks)
+      j = 0;
+    swap_block_next = j;
+  }
+
+  return true;
+}
+
+void swap_block_free(int *blocks, int size) {
+  int i, j, k;
+
+  for (i = 0; i < size; ++i) {
+    j = blocks[i];
+    assert(j >= 0 && j < n_swap_blocks);
+    k = j & 7;
+    j >>= 3;
+    assert((swap_block_bitmap[j] & bits[k]) == 0);
+    swap_block_bitmap[j] |= bits[k];
+#ifndef NDEBUG
+    blocks[i] = 0xaaaaaaaa;
+#endif    
+  }
 }
+#endif
 
 // swap address complemented wrt. pool and native wrt. backing store
 void swap_read(int swap_base, int core_base, int size) {
  printf("swap_read swap [%d,%d) to core [%d,%d)\n", swap_base, swap_base + size, core_base, core_base + size);
+#ifdef INDIRECT_SWAP
+ printf("blocks");
+#endif
   for (int i = 0; i < size; ++i) {
-    assert(core_table_mem[core_base + i] == 0xaaaaaaaa);
-    core_table_mem[core_base + i] = swap_table_mem[swap_base + i];
+#ifdef INDIRECT_SWAP
+    int block = swap_table_mem[swap_base + i];
+ printf(" %d", block);
+    int data = swap_block_mem[block];
+    swap_block_mem[block] = 0x55555555;
+#else
+    int data = swap_table_mem[swap_base + i];
     swap_table_mem[swap_base + i] = 0xaaaaaaaa;
+#endif
+    assert(core_table_mem[core_base + i] == 0xaaaaaaaa);
+    core_table_mem[core_base + i] = data;
   }
+#ifdef INDIRECT_SWAP
+ printf("\n");
+#endif
 }
 
 // swap address complemented wrt. pool and native wrt. backing store
 void swap_write(int swap_base, int core_base, int size) {
  printf("swap_write core [%d,%d) to swap [%d,%d)\n", core_base, core_base + size, swap_base, swap_base + size);
+#ifdef INDIRECT_SWAP
+ printf("blocks");
+#endif
   for (int i = 0; i < size; ++i) {
-    assert(swap_table_mem[swap_base + i] == 0xaaaaaaaa);
-    swap_table_mem[swap_base + i] = core_table_mem[core_base + i];
+    int data = core_table_mem[core_base + i];
     core_table_mem[core_base + i] = 0xaaaaaaaa;
+#ifdef INDIRECT_SWAP
+    int block = swap_table_mem[swap_base + i];
+ printf(" %d", block);
+    assert(block >= 0 && block < n_swap_blocks);
+    assert(swap_block_mem[block] == 0x55555555);
+    swap_block_mem[block] = data;
+#else
+    assert(swap_table_mem[swap_base + i] == 0xaaaaaaaa);
+    swap_table_mem[swap_base + i] = data;
+#endif
   }
+#ifdef INDIRECT_SWAP
+ printf("\n");
+#endif
 }

diff --git a/swap.h b/swap.h
index 03c786c..9e6d3a4 100644 (file)
--- a/swap.h
+++ b/swap.h
@@ -1,9 +1,11 @@
 #ifndef _SWAP_H
 #define _SWAP_H 1
 
+#include <stdint.h>
 #include "pool.h"
 
-#define MOVEABLE_SWAP 1
+#define INDIRECT_SWAP 1
+//#define MOVEABLE_SWAP 1
 
 #ifdef MOVEABLE_SWAP
 #define swap_table_alloc(item, size) \
@@ -18,10 +20,24 @@
 #endif
 #define swap_table_free(item) pool_free(&swap_table, item)
 
+#ifdef INDIRECT_SWAP
+extern uint8_t *swap_block_bitmap;
+extern int swap_block_next;
+
+extern int *swap_block_mem;
+extern int n_swap_blocks;
+#endif
+
 extern struct pool_head swap_table;
 extern int *swap_table_mem;
 
+#ifdef INDIRECT_SWAP
+void swap_init(int n_table, int table_spare, int n_blocks);
+bool swap_block_alloc(int *blocks, int size);
+void swap_block_free(int *blocks, int size);
+#else
 void swap_init(int n_table, int table_spare);
+#endif
 void swap_read(int swap_base, int core_base, int size);
 void swap_write(int swap_base, int core_base, int size);