ref: 9124769c0c1e7cb18b06be4ade8aa376dd457f04
parent: 3971bc6b760a0658b27d0dd0f46693129ff59164
author: Noam Preil <noam@pixelhero.dev>
date: Fri Mar 22 19:57:45 EDT 2024
WORKING CACHE LESSGOOOOO
--- a/cache.c
+++ b/cache.c
@@ -5,20 +5,24 @@
typedef struct {Lock;
- // index into raw cache
- u32int index[7];
- // 24 bits of value index plus 8 bits of fd
- u32int value[7];
+ // arena-local block index | arena index << 16
+ u32int index[8];
+ u8int values[8*3];
} bucket_t;
#pragma pack off
-typedef char mainentry_t[8192];
-static mainentry_t *data;
+static char *data;
static bucket_t *buckets, *bucketend;
static u32int *freelist;
static u32int freelen;
static Lock freelock;
+#define NENTRIES 8
+#define ENTRIES 0x10000
+// Oversizes, but ensures power-of-two for fibonacci hashing
+#define BUCKETS (ENTRIES/4)
+#define BITS 56
+
void
cacheinit(void)
{@@ -25,11 +29,11 @@
usize displacement;
assert(sizeof(Lock) == 8);
assert(sizeof(bucket_t) == 64);
- data = sbrk(8192 * 128*1024);
+ data = sbrk(8192 * ENTRIES);
// 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);
+ buckets = sbrk(64 + 64*BUCKETS);
+ freelist = sbrk(4 * ENTRIES);
displacement = ((usize)buckets & 0b111111);
if(displacement != 0){displacement = 64 - displacement;
@@ -37,8 +41,8 @@
}
// alignment
assert(((usize)buckets&0b111111) == 0);
- bucketend = buckets + 32768;
- freelen = 128*1024;
+ bucketend = buckets + BUCKETS;
+ freelen = ENTRIES;
for(u32int i = 0; i < freelen; i += 1){freelist[i] = i;
}
@@ -63,20 +67,28 @@
return result;
}
-// Called to indicate that a read has been finished.
+// Called to indicate that a request has been finished.
// See documentation at top of file for more details.
void
-cachewritten(int fd, u32int blockindex)
+cachedone(u16int arenaindex, u16int blockindex)
{u64int bucketindex;
bucket_t *bucket;
u32int key;
- assert(fd < 0xFF);
- key = (blockindex << 8) | fd;
+ key = arenaindex<<16 | blockindex;
// We have 32K buckets, so we want 15 bits
- bucketindex = ((u64int)key * 11400714819323198485LL) >> 49;
+ bucketindex = ((u64int)key * 11400714819323198485LL) >> BITS;
bucket = &buckets[bucketindex];
- unlock(bucket);
+ // Need to do linear probing to find the right bucket to unlock
+ for(;;){+ for(int i = 0; i < NENTRIES; i += 1){+ if(bucket->index[i] == key){+ unlock(bucket);
+ return;
+ }
+ }
+ bucket++;
+ }
}
// Looks up a cache entry. If the entry is not present in cache,
@@ -84,34 +96,35 @@
// 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)
+cachelookup(char **buf, u16int arenaindex, u32int blockindex)
{u64int bucketindex;
u32int cacheindex;
bucket_t *bucket;
u32int key;
- assert(fd < 0xFF);
- key = (blockindex << 8) | fd;
+ assert(blockindex < 0x10000);
+ key = arenaindex << 16 | (blockindex&0xFFFF);
// We have 32K buckets, so we want 15 bits
- bucketindex = ((u64int)key * 11400714819323198485LL) >> 49;
- print("GET bucket index: %llx\n", bucketindex);+ bucketindex = ((u64int)key * 11400714819323198485LL) >> BITS;
bucket = &buckets[bucketindex];
while(bucket != bucketend){lock(bucket);
- for(int i = 0; i < 7; i += 1){+ for(int i = 0; i < NENTRIES; i += 1){ if(bucket->index[i] == 0){// Key does not exist
cacheindex = grabfree();
- *buf = (char*)(data + cacheindex);
+ *buf = &data[cacheindex*8192];
assert((cacheindex & 0xFF000000) == 0);
- bucket->index[i] = blockindex;
- bucket->value[i] = (cacheindex << 8) | fd;
+ bucket->index[i] = key;
+ bucket->values[i*3] = cacheindex&0xFF;
+ bucket->values[i*3+1] = (cacheindex>>8)&0xFF;
+ bucket->values[i*3+2] = cacheindex>>16;
// 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);
+ if(bucket->index[i] == key){+ u32int cacheindex = bucket->values[i*3] | (bucket->values[i*3+1]<<8) | (bucket->values[i*3+2]<<16);
+ *buf = &data[cacheindex * 8192];
return 1;
}
}
@@ -118,6 +131,8 @@
unlock(bucket);
bucket++;
}
+//FIXME not unreachable
+//if the final bucket is full, we must handle it
sysfatal("unreachable");return 0;
}
--- a/disk.c
+++ b/disk.c
@@ -120,15 +120,18 @@
// Reads one block from disk into the cache, returning a pointer into the
// cache.
// If the data is already in cache, it will not be read again.
-// Caller is responsible for calling cachedone(buf);
+// Caller is responsible for calling cachedone(arena->fd, blockindex);
char*
vtreadarenablock(VtArena *arena, u32int blockindex)
{char *buf;
- if(!cachelookup(&buf, arena->fd, blockindex)){- if(pread(arena->fd, buf, arena->blocksize, arena->base+(blockindex*arena->blocksize)) != arena->blocksize)
+ if(arena->blocksize != 8192)
+ sysfatal("invalid blocksize %d\n", arena->blocksize);+ if(!cachelookup(&buf, arena->index, blockindex)){+ if(pread(arena->fd, buf, arena->blocksize, arena->base+(blockindex*arena->blocksize)) != arena->blocksize){+ cachedone(arena->index, blockindex);
return nil;
- cachewritten(arena->fd, blockindex);
+ }
}
return buf;
}
@@ -154,7 +157,8 @@
m = arena->blocksize - off;
if(m > size - n)
m = size - n;
- memmove(&dbuf[n], &buf[off], m);
+ memcpy(&dbuf[n], &buf[off], m);
+ cachedone(arena->index, addr/arena->blocksize);
n += m;
off = 0;
addr += arena->blocksize;
@@ -170,8 +174,11 @@
vtreadarena(addr.s_arena, addr.offset, buf, size);
size = U16GET(buf+7);
if(buf[29] == 2){- if(unwhack(dst, size, buf+38, U16GET(buf+5)) != size)
- sysfatal("decompression failed: %r");+ if(unwhack(dst, size, buf+38, U16GET(buf+5)) != size){+ free(buf);
+ sysfatal("decompression failed: %r. block index %llx", addr.offset/addr.s_arena->blocksize);+ return 0;
+ }
} else if(buf[29] == 1)
memcpy(dst, buf+38, size);
free(buf);
@@ -246,8 +253,10 @@
arenas = realloc(arenas, sizeof(VtArena) * (nmap + numarenas));
if(!arenas)
sysfatal("oom");- for(; nmap > 0; nmap -= 1)
+ for(; nmap > 0; nmap -= 1){+ arenas[numarenas].index = numarenas;
initarena(&arenas[numarenas++], fd, map[nmap-1], blocksize);
+ }
free(map);
}
--- a/mkfile
+++ b/mkfile
@@ -9,6 +9,8 @@
</sys/src/cmd/mkmany
+LDFLAGS=-p
+
vac:VE:
vacfs -h tcp!127.1!14011 vac:4091f8b8aafc7b8a815f38534b70a171e4ae3e44
--- a/neoventi.c
+++ b/neoventi.c
@@ -1,9 +1,12 @@
#include <u.h>
#include <libc.h>
+#include <pool.h>
#include <bio.h>
#include <thread.h>
#include "neoventi.h"
+int mainstacksize = 128*1024;
+
void
parseargs(int argc, char **argv)
{@@ -23,6 +26,9 @@
validate(void)
{fprint(2, "TODO: validate initial state");
+ for(int i = 0; i < 1000; i += 1){+ poolcheck(mainmem);
+ }
}
void
--- a/neoventi.h
+++ b/neoventi.h
@@ -57,6 +57,8 @@
u32int blocksize;
u32int version;
u32int ctime, wtime;
+ // used for caching. only 64K arenas may reside in the cache at a time.
+ u16int index;
/* disk info */
u64int size;
@@ -130,5 +132,5 @@
void initarenas(void);
void initindex(void);
void cacheinit(void);
-int cachelookup(char **buf, int fd, u32int blockindex);
-void cachewritten(int fd, u32int blocksize);
\ No newline at end of file
+int cachelookup(char **buf, u16int arenaindex, u32int blockindex);
+void cachedone(u16int arenaindex, u16int blockindex);
\ No newline at end of file
--- a/notebook
+++ b/notebook
@@ -865,3 +865,25 @@
We still need a way to track buffer references, though. We can stuff a secret eight bytes before each buffer, and then just atomically increment it? For now, lacking atomics, we can toss a lock and adjust it under the lock. Entries can only be reclaimed when they have no active readers.
Ooh, one option for tracking readers without too much locking is to have a list of items being read. Could be designed to fit pretty cmpactly, and should never be huge, since we don't expect to have more than a dozen active readers at once. Might be easier to manage.
+
+...short term, can just lock the bucket during a read, too? That doesn't help for evictions, though? Ah, sure it does; pick a random bucket, try to lock it, advance until we find a bucket we can lock, evict its first entry >_> Suboptimal, but might work.
+
+and, having cachedone require the fd and block index instead of the buffer is not great.
+
+With the cache disabled as follows, I measured time to walk the fossil root I've been using for testing.
+
+char*
+vtreadarenablock(VtArena *arena, u32int blockindex)
+{+ char *buf = malloc(8192);
+// if(!cachelookup(&buf, arena->fd, blockindex)){+ if(pread(arena->fd, buf, arena->blocksize, arena->base+(blockindex*arena->blocksize)) != arena->blocksize)
+ return nil;
+ //}
+ return buf;
+}
+
+It took 29.96s.
+
+With the cache enabled, I get a compression error >_>
+
--- a/server.c
+++ b/server.c
@@ -1,6 +1,7 @@
#include <u.h>
#include <libc.h>
#include <bio.h>
+#include <pool.h>
#include <thread.h>
#include "neoventi.h"
@@ -54,10 +55,14 @@
{char c;
// Response is one line of unknown size; discard bytes until EOL
- if(fprint(conn.fd, "venti-02-neoventi\n") == 18)
- while(read(conn.fd, &c, 1) == 1)
- if(c == '\n')
+ if(fprint(conn.fd, "venti-02-neoventi\n") == 18){+ while(read(conn.fd, &c, 1) == 1){+ if(c == '\n'){+ poolcheck(mainmem);
return;
+ }
+ }
+ }
// If the handshake fails, make it clear there's a problem and give up
fprint(conn.fd, "FUCK OFF\n");
vterr(conn, nil, "handshake failed");
@@ -136,6 +141,7 @@
case 1:
fprint(2, "abandoning client: %r\n");
case 2:
+ exits(nil);
return 0;
default:
fprint(2, "internal error: unexpected bounce code\n");
@@ -165,7 +171,8 @@
fprint(2, "failed to accept connection\n");
return;
}
- proccreate(handleproc, (void*)fd, mainstacksize);
+ handleproc((void*)fd);
+// proccreate(handleproc, (void*)fd, mainstacksize);
}
void