Turn things around so that swap is written from top down

diff --git a/Makefile b/Makefile
index 04a7e44..081a63d 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,5 @@
-CFLAGS=-g -Wall -D__FUZIX__ -DNDEBUG
+CFLAGS=-g -Wall -D__FUZIX__
+# -DNDEBUG
 
 all: pool_test_gen pool_test_run process_test_gen process_test_run mkfs \
 inode_test_gen inode_test_run

diff --git a/block_pool.c b/block_pool.c
index 3c61d68..cc28091 100644 (file)
--- a/block_pool.c
+++ b/block_pool.c
@@ -1,4 +1,5 @@
 #include <assert.h>
+#include <stdio.h> // temporary
 #include <stdlib.h>
 #include <string.h>
 #include "block_pool.h"
@@ -36,11 +37,21 @@ bool block_pool_alloc(struct block_pool *block_pool, int *table, int size) {
     loop_entry:
       if (c) goto found;
     }
+#if 1
     for (j = 0; ; ++j) {
       assert(j <= block_pool->next >> 3);
       c = block_pool->bitmap[j];
       if (c) goto found;
     }
+#else
+    k = (block_pool->next >> 3) + 1;
+    for (j = 0; j < k; ++j) {
+      c = block_pool->bitmap[j];
+      if (c) goto found;
+    }
+    core_block_free(table, i);
+    return false;
+#endif
 
   found:
     for (k = 0; (c & 1) == 0; ++k)
@@ -48,7 +59,11 @@ bool block_pool_alloc(struct block_pool *block_pool, int *table, int size) {
     block_pool->bitmap[j] &= ~bits[k];
     block_pool->next = (j << 3) | k;
 
+#ifndef NDEBUG // makes us remove the following line in gen.sh as appropriate
     assert(table[i] == 0x55555555);
+#endif
+ //printf("block_pool %p table+i %p alloc %d\n", block_pool, table + i, block_pool->next);
+ fflush(stdout);
     table[i] = block_pool->next++;
     if (block_pool->next >= block_pool->n_blocks)
       block_pool->next = 0;
@@ -63,12 +78,16 @@ void block_pool_free(struct block_pool *block_pool, int *table, int size) {
 
   for (i = 0; i < size; ++i) {
     j = table[i];
+ //printf("block_pool %p table+i %p free %d\n", block_pool, table + i, j);
+ fflush(stdout);
     assert(j >= 0 && j < block_pool->n_blocks);
     k = j & 7;
     j >>= 3;
     assert((block_pool->bitmap[j] & bits[k]) == 0);
     block_pool->bitmap[j] |= bits[k];
+#ifndef NDEBUG
     table[i] = 0x55555555;
+#endif
   }
 
   block_pool->avail += size;

diff --git a/core.h b/core.h
index 506f786..a596e20 100644 (file)
--- a/core.h
+++ b/core.h
@@ -1,7 +1,7 @@
 #ifndef _CORE_H
 #define _CORE_H 1
 
-#define INDIRECT_CORE 1
+//#define INDIRECT_CORE 1
 
 #include <stdint.h>
 #ifdef INDIRECT_CORE

diff --git a/process.c b/process.c
index 139a2c7..8ca4ed2 100644 (file)
--- a/process.c
+++ b/process.c
@@ -121,14 +121,14 @@ static bool do_swap_out(int swap_out) {
 
     loop_entry:
       // calculate transfer parameters
-      swap_base = victim->swap_item.base + victim_swap_blocks;
+      victim_core_blocks -= blocks;
+      victim_swap_blocks += blocks;
+      swap_base = victim->swap_item.limit - victim_swap_blocks;
 #ifndef INDIRECT_CORE
-      core_base = victim->core_item.base;
+      core_base = victim->core_item.limit - blocks;
 #else /* INDIRECT_CORE */
-      core_base = victim->core_item.base + victim_swap_blocks;
+      core_base = victim->core_item.limit - victim_swap_blocks;
 #endif /* INDIRECT_CORE */
-      victim_core_blocks -= blocks;
-      victim_swap_blocks += blocks;
       size = (long)blocks << BLOCK_SHIFT;
 
       // transfer data to swap
@@ -228,7 +228,6 @@ static bool do_swap_out(int swap_out) {
             &core_table,
             &victim->core_item,
             victim_core_blocks,
-            POOL_ALLOC_MODE_LAST_FIT |
               POOL_ALLOC_MODE_MOVEABLE |
               POOL_ALLOC_MODE_REALLOC
           )
@@ -511,7 +510,6 @@ void process_run(struct process *process) {
           &core_table,
           &process->core_item,
           process_core_blocks + blocks,
-          POOL_ALLOC_MODE_LAST_FIT |
             POOL_ALLOC_MODE_MOVEABLE |
             POOL_ALLOC_MODE_REALLOC
         )
@@ -520,14 +518,14 @@ void process_run(struct process *process) {
 
     loop_entry_full:
       // calculate transfer parameters
-      process_core_blocks += blocks;
-      process_swap_blocks -= blocks;
-      swap_base = process->swap_item.base + process_swap_blocks;
+      swap_base = process->swap_item.limit - process_swap_blocks;
 #ifndef INDIRECT_CORE
-      core_base = process->core_item.base;
+      core_base = process->core_item.limit - blocks;
 #else /* INDIRECT_CORE */
-      core_base = process->core_item.base + process_swap_blocks;
+      core_base = process->core_item.limit - process_swap_blocks;
 #endif /* INDIRECT_CORE */
+      process_core_blocks += blocks;
+      process_swap_blocks -= blocks;
       size = (long)blocks << BLOCK_SHIFT;
 
       // transfer data to core
@@ -658,7 +656,7 @@ void process_free(struct process *process) {
   else if (process == victim) {
     // victim, remove from core and swap pools
 #ifdef INDIRECT_SWAP
-    swap_base = victim->swap_item.base;
+    swap_base = victim->swap_item.limit - victim_swap_blocks;
     block_pool_free(
       &swap_block_pool,
       swap_table_mem + swap_base,
@@ -668,11 +666,11 @@ void process_free(struct process *process) {
 #ifndef INDIRECT_CORE
     pool_free(&core_table, &victim->core_item);
 #else /* INDIRECT_CORE */
-    core_base = victim->core_item.base + victim_swap_blocks;
+    core_base = victim->core_item.base;
     block_pool_free(
       &core_block_pool,
       core_table_mem + core_base,
-      victim->core_item.limit - core_base
+      victim->core_item.limit - core_base - victim_swap_blocks
     );
 #endif /* INDIRECT_CORE */
     victim = NULL;

diff --git a/process_test_run.c b/process_test_run.c
index 006f84b..638d121 100644 (file)
--- a/process_test_run.c
+++ b/process_test_run.c
@@ -19,7 +19,7 @@ void core_hash_init(int process, long base, long size, long offset) {
   long i, addr;
   long long hash;
 
- printf("core_hash_init %d %ld(%d) %ld(%d) %ld(%d)\n", process, base, (int)(base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT), offset, (int)(offset >> BLOCK_SHIFT));
+ //printf("core_hash_init %d %ld(%d) %ld(%d) %ld(%d)\n", process, base, (int)(base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT), offset, (int)(offset >> BLOCK_SHIFT));
   for (i = 0L; i < size; ++i) {
     addr = base + i;
 #ifdef INDIRECT_CORE
@@ -41,7 +41,7 @@ void core_hash_verify(int process, long base, long size, long offset) {
   long i, addr;
   long long hash;
 
- printf("core_hash_verify %d %ld(%d) %ld(%d) %ld(%d)\n", process, base, (int)(base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT), offset, (int)(offset >> BLOCK_SHIFT));
+ //printf("core_hash_verify %d %ld(%d) %ld(%d) %ld(%d)\n", process, base, (int)(base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT), offset, (int)(offset >> BLOCK_SHIFT));
   for (i = 0L; i < size; ++i) {
     addr = base + i;
 #ifdef INDIRECT_CORE
@@ -59,11 +59,11 @@ void core_hash_verify(int process, long base, long size, long offset) {
   }
 }
 
-void swap_hash_verify(int process, long base, long size) {
+void swap_hash_verify(int process, long base, long size, long offset) {
   long i, addr;
   long long hash;
 
- printf("swap_hash_verify %d %ld(%d) %ld(%d)\n", process, base, (int)(base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
+ //printf("swap_hash_verify %d %ld(%d) %ld(%d) %ld(%d)\n", process, base, (int)(base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT), offset, (int)(offset >> BLOCK_SHIFT));
   for (i = 0L; i < size; ++i) {
     addr = base + i;
 #ifdef INDIRECT_SWAP
@@ -71,7 +71,7 @@ void swap_hash_verify(int process, long base, long size) {
       (swap_table_mem[addr >> BLOCK_SHIFT] << BLOCK_SHIFT) |
       (addr & (BLOCK_SIZE - 1));
 #endif /* INDIRECT_SWAP */
-    hash = process * 17 + i * 29;
+    hash = process * 17 + (i + offset) * 29;
     hash = (hash & 0xffffffffLL) + (hash >> 32);
     hash = (hash & 0xffffLL) + (hash >> 16);
     hash = (hash & 0xffLL) + (hash >> 8);
@@ -85,7 +85,7 @@ void swap_hash_verify(int process, long base, long size) {
 void core_copy(long src_base, long dest_base, long size) {
   long i;
 
- printf("core_copy %ld(%d) %ld(%d) %ld(%d)\n", src_base, (int)(src_base >> BLOCK_SHIFT), dest_base, (int)(dest_base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
+ //printf("core_copy %ld(%d) %ld(%d) %ld(%d)\n", src_base, (int)(src_base >> BLOCK_SHIFT), dest_base, (int)(dest_base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
   for (i = 0L; i < size; ++i) {
     core_block_mem[dest_base + i] = core_block_mem[src_base + i];
     core_block_mem[src_base + i] = 0xaa;
@@ -95,7 +95,7 @@ void core_copy(long src_base, long dest_base, long size) {
 void core_copy_up(long src_limit, long dest_limit, long size) {
   long i;
 
- printf("core_copy_up %ld(%d) %ld(%d) %ld(%d)\n", src_limit, (int)(src_limit >> BLOCK_SHIFT), dest_limit, (int)(dest_limit >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
+ //printf("core_copy_up %ld(%d) %ld(%d) %ld(%d)\n", src_limit, (int)(src_limit >> BLOCK_SHIFT), dest_limit, (int)(dest_limit >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
   size = -size;
   for (i = -1L; i >= size; --i) {
     core_block_mem[dest_limit + i] = core_block_mem[src_limit + i];
@@ -108,7 +108,7 @@ void core_copy_up(long src_limit, long dest_limit, long size) {
 void swap_copy(long src_base, long dest_base, long size) {
   long i;
 
- printf("swap_copy %ld(%d) %ld(%d) %ld(%d)\n", src_base, (int)(src_base >> BLOCK_SHIFT), dest_base, (int)(dest_base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
+ //printf("swap_copy %ld(%d) %ld(%d) %ld(%d)\n", src_base, (int)(src_base >> BLOCK_SHIFT), dest_base, (int)(dest_base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
   for (i = 0; i < size; ++i) {
     swap_block_mem[dest_base + i] = swap_block_mem[src_base + i];
     swap_block_mem[src_base + i] = 0xaa;
@@ -118,7 +118,7 @@ void swap_copy(long src_base, long dest_base, long size) {
 void swap_copy_up(long src_limit, long dest_limit, long size) {
   long i;
 
- printf("swap_copy_up %ld(%d) %ld(%d) %ld(%d)\n", src_limit, (int)(src_limit >> BLOCK_SHIFT), dest_limit, (int)(dest_limit >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
+ //printf("swap_copy_up %ld(%d) %ld(%d) %ld(%d)\n", src_limit, (int)(src_limit >> BLOCK_SHIFT), dest_limit, (int)(dest_limit >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
   size = -size;
   for (i = -1; i >= size; --i) {
     swap_block_mem[dest_limit + i] = swap_block_mem[src_limit + i];
@@ -130,7 +130,7 @@ void swap_copy_up(long src_limit, long dest_limit, long size) {
 void core_to_swap_copy(long src_base, long dest_base, long size) {
   long i;
 
- printf("core_to_swap_copy %ld(%d) %ld(%d) %ld(%d)\n", src_base, (int)(src_base >> BLOCK_SHIFT), dest_base, (int)(dest_base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
+ //printf("core_to_swap_copy %ld(%d) %ld(%d) %ld(%d)\n", src_base, (int)(src_base >> BLOCK_SHIFT), dest_base, (int)(dest_base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
   for (i = 0; i < size; ++i)
     rassert(swap_block_mem[dest_base + i] == 0xaa);
   memcpy(swap_block_mem + dest_base, core_block_mem + src_base, size);
@@ -140,7 +140,7 @@ void core_to_swap_copy(long src_base, long dest_base, long size) {
 void swap_to_core_copy(long src_base, long dest_base, long size) {
   long i;
 
- printf("swap_to_core_copy %ld(%d) %ld(%d) %ld(%d)\n", src_base, (int)(src_base >> BLOCK_SHIFT), dest_base, (int)(dest_base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
+ //printf("swap_to_core_copy %ld(%d) %ld(%d) %ld(%d)\n", src_base, (int)(src_base >> BLOCK_SHIFT), dest_base, (int)(dest_base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT));
   for (i = 0; i < size; ++i)
     rassert(core_block_mem[dest_base + i] == 0xaa);
   memcpy(core_block_mem + dest_base, swap_block_mem + src_base, size);
@@ -430,33 +430,33 @@ int main(int argc, char **argv) {
         }
         if (processes[test.process].lru_item.prev != NULL) { // fully in core
           assert(processes + test.process != victim);
-          swap_base = -1;
-          swap_blocks = 0;
-          swap_size = 0L;
           core_base = processes[test.process].core_item.base;
           core_blocks = processes[test.process].core_item.limit - core_base;
           core_size = processes[test.process].size;
+          swap_base = -1;
+          swap_blocks = 0;
+          swap_size = 0L;
         }
         else {
           if (processes + test.process == victim) { // victim
-            swap_base = victim->swap_item.base;
-            swap_blocks = victim_swap_blocks;
-            swap_size = swap_blocks << BLOCK_SHIFT;
-#ifndef INDIRECT_CORE
             core_base = victim->core_item.base;
+#ifndef INDIRECT_CORE
+            core_blocks = victim->core_item.limit - core_base;
 #else /* INDIRECT_CORE */
-            core_base = victim->core_item.base + swap_blocks;
+            core_blocks = victim->core_item.limit - core_base - victim_swap_blocks;
 #endif /* INDIRECT_CORE */
-            core_blocks = victim->core_item.limit - core_base;
-            core_size = victim->size - swap_size;
+            core_size = core_blocks << BLOCK_SHIFT;
+            swap_base = victim->swap_item.limit - victim_swap_blocks;
+            swap_blocks = victim_swap_blocks;
+            swap_size = victim->size - core_size;
           }
           else { // fully in swap
-            swap_base = processes[test.process].swap_item.base;
-            swap_blocks = processes[test.process].swap_item.limit - swap_base;
-            swap_size = processes[test.process].size;
             core_base = -1;
             core_blocks = 0;
             core_size = 0L;
+            swap_base = processes[test.process].swap_item.base;
+            swap_blocks = processes[test.process].swap_item.limit - swap_base;
+            swap_size = processes[test.process].size;
           }
         }
         rassert(core_blocks + swap_blocks == actual_old_blocks);
@@ -466,12 +466,13 @@ int main(int argc, char **argv) {
           test.process,
           (long)core_base << BLOCK_SHIFT,
           core_size,
-          swap_size
+          0 
         );
         swap_hash_verify(
           test.process,
           (long)swap_base << BLOCK_SHIFT,
-          swap_size
+          swap_size,
+          core_size
         );
         process_free(processes + test.process);
         processes[test.process].size = -1L;
@@ -489,33 +490,33 @@ done:
     else {
       if (processes[i].lru_item.prev != NULL) { // fully in core
         assert(processes + i != victim);
-        swap_base = -1;
-        swap_blocks = 0;
-        swap_size = 0L;
         core_base = processes[i].core_item.base;
         core_blocks = processes[i].core_item.limit - core_base;
         core_size = processes[i].size;
+        swap_base = -1;
+        swap_blocks = 0;
+        swap_size = 0L;
       }
       else {
         if (processes + i == victim) { // victim
-          swap_base = victim->swap_item.base;
-          swap_blocks = victim_swap_blocks;
-          swap_size = swap_blocks << BLOCK_SHIFT;
-#ifndef INDIRECT_CORE
           core_base = victim->core_item.base;
+#ifndef INDIRECT_CORE
+          core_blocks = victim->core_item.limit - core_base;
 #else /* INDIRECT_CORE */
-          core_base = victim->core_item.base + swap_blocks;
+          core_blocks = victim->core_item.limit - core_base - victim_swap_blocks;
 #endif /* INDIRECT_CORE */
-          core_blocks = victim->core_item.limit - core_base;
-          core_size = victim->size - swap_size;
+          core_size = core_blocks << BLOCK_SHIFT;
+          swap_base = victim->swap_item.limit - victim_swap_blocks;
+          swap_blocks = victim_swap_blocks;
+          swap_size = victim->size - core_size;
         }
         else { // fully in swap
-          swap_base = processes[i].swap_item.base;
-          swap_blocks = processes[i].swap_item.limit - swap_base;
-          swap_size = processes[i].size;
           core_base = -1;
           core_blocks = 0;
           core_size = 0L;
+          swap_base = processes[i].swap_item.base;
+          swap_blocks = processes[i].swap_item.limit - swap_base;
+          swap_size = processes[i].size;
         }
       }
       rassert(
@@ -534,7 +535,7 @@ done:
         i,
         (long)core_base << BLOCK_SHIFT,
         core_size,
-        swap_size
+        0
       );
 #ifdef INDIRECT_CORE
       block_pool_free(
@@ -546,7 +547,8 @@ done:
       swap_hash_verify(
         i,
         (long)swap_base << BLOCK_SHIFT,
-        swap_size
+        swap_size,
+        core_size
       );
 #ifdef INDIRECT_SWAP
       block_pool_free(