ref: d42b5ae9b1b41d92fb88cffa6bdb930c2b476570
parent: aa74602e266a6443d8b49ef85241f5f1bfbc5d07
author: Noam Preil <noam@pixelhero.dev>
date: Mon Feb 26 03:16:09 EST 2024
forgot to add cache.c
--- /dev/null
+++ b/cache.c
@@ -1,0 +1,123 @@
+#include <u.h>
+#include <libc.h>
+
+#pragma pack on
+
+typedef struct {+ Lock;
+ // index into raw cache
+ u32int index[7];
+ // 24 bits of value index plus 8 bits of fd
+ u32int value[7];
+} bucket_t;
+#pragma pack off
+
+typedef char mainentry_t[8192];
+static mainentry_t *data;
+static bucket_t *buckets, *bucketend;
+static u32int *freelist;
+static u32int freelen;
+static Lock freelock;
+
+void
+cacheinit(void)
+{+ usize displacement;
+ assert(sizeof(Lock) == 8);
+ assert(sizeof(bucket_t) == 64);
+ data = sbrk(8192 * 128*1024);
+ // 18725 buckets is the minimum for 128K entries; we round up to 32,768. That "wastes" ~1MiB, but spreads entries out further,
+ // and gives a nice power of two for fibonacci hashing.
+ buckets = sbrk(64 + 64*32768);
+ freelist = sbrk(4 * 128*1024);
+ displacement = ((usize)buckets & 0b111111);
+ if(displacement != 0){+ displacement = 64 - displacement;
+ buckets = (bucket_t*)((usize)buckets + displacement);
+ }
+ // alignment
+ assert(((usize)buckets&0b111111) == 0);
+ bucketend = buckets + 32768;
+ freelen = 128*1024;
+ for(u32int i = 0; i < freelen; i += 1){+ freelist[i] = i;
+ }
+}
+
+// Grabs a free cache entry, evicting if necessary.
+u32int
+grabfree(void)
+{+ u32int result;
+ lock(&freelock);
+ // For now, block until something is free.
+ // This is terrible. FIXME
+ while(freelen == 0){+ unlock(&freelock);
+ sleep(50);
+ lock(&freelock);
+ }
+ freelen -= 1;
+ result = freelist[freelen];
+ unlock(&freelock);
+ return result;
+}
+
+// Called to indicate that a read has been finished.
+// See documentation at top of file for more details.
+void
+cachewritten(int fd, u32int blockindex)
+{+ u64int bucketindex;
+ bucket_t *bucket;
+ u32int key;
+ assert(fd < 0xFF);
+ key = (blockindex << 8) | fd;
+ // We have 32K buckets, so we want 15 bits
+ bucketindex = ((u64int)key * 11400714819323198485LL) >> 49;
+ bucket = &buckets[bucketindex];
+ unlock(bucket);
+}
+
+// Looks up a cache entry. If the entry is not present in cache,
+// this grabs a free buffer, inserts it into cache, and yields
+// its index so that the caller may fill it up.
+// Returns whether the data was already in cache.
+int
+cachelookup(char **buf, int fd, u32int blockindex)
+{+ u64int bucketindex;
+ u32int cacheindex;
+ bucket_t *bucket;
+ u32int key;
+ assert(fd < 0xFF);
+ key = (blockindex << 8) | fd;
+ // We have 32K buckets, so we want 15 bits
+ bucketindex = ((u64int)key * 11400714819323198485LL) >> 49;
+ print("GET bucket index: %llx\n", bucketindex);+ bucket = &buckets[bucketindex];
+ while(bucket != bucketend){+ lock(bucket);
+ for(int i = 0; i < 7; i += 1){+ if(bucket->index[i] == 0){+ // Key does not exist
+ cacheindex = grabfree();
+ *buf = (char*)(data + cacheindex);
+ assert((cacheindex & 0xFF000000) == 0);
+ bucket->index[i] = blockindex;
+ bucket->value[i] = (cacheindex << 8) | fd;
+ // Leaves bucket locked intentionally!
+ return 0;
+ }
+ if(bucket->index[i] == blockindex && (bucket->value[i] & 0xff) == fd){+ *buf = (char*)(data + (bucket->value[i] >> 8));
+ unlock(bucket);
+ return 1;
+ }
+ }
+ unlock(bucket);
+ bucket++;
+ }
+ sysfatal("unreachable");+ return 0;
+}
--
⑨