>>45
I scrapped it long ago, when I discovered Lisp. It had some regexp like capability, where instead of function call regepx matching was done.
Most of the code was just crud like...
// Page System
#include <string.h>
#include "ps.h"
#include "mm.h"
#include "im.h"
#define HEADER_SIZE MM_PAGE_SIZE
#define PAGE_SIZE MM_PAGE_SIZE
#define OFF_BITS CBITS(PAGE_SIZE-1)
#define PTE_SIZE 32 /* page table entry size */
typedef struct {
char magic[8];
u8 version;
u8 im_size; // image size
u8 npages;
u8 pt_size; // page table size
u8 pt_off;
u8 pages_off; // offset of pages area
} Header;
static u1 header[HEADER_SIZE];
#define h (*(Header*)header)
typedef struct {
u8 len;
u8 next;
} Pte;
#define PTE(n,w) ((Pte*)(mm_a(h.pt_off+(n)*PTE_SIZE,w)))
void ps_init() {
mm_r(header, 0, HEADER_SIZE);
}
void ps_quit() {
mm_w(0, header, HEADER_SIZE);
}
void ps_format() {
Pte *e;
strcpy(h.magic, "SYMTERA");
h.version = 0;
h.im_size = im_get_size();
// -1 is required for h.pages_off alignment
h.npages = (h.im_size-HEADER_SIZE)/(PAGE_SIZE+PTE_SIZE) - 1;
h.pt_size = h.npages*PTE_SIZE;
h.pt_off = HEADER_SIZE;
h.pages_off = ((h.pt_off+h.pt_size+PAGE_SIZE-1) /
PAGE_SIZE)*PAGE_SIZE;
e = PTE(0,1);
e->len = 0;
e->next = 1;
e = PTE(1,1);
e->len = h.npages-1;
e->next = 0;
mm_w(0, header, HEADER_SIZE);
}
u8 ps_alloc(int npages) {
Pte *e, *ne;
u8 pn, n;
for(n = 0; ; pn = n, n = e->next) {
e = PTE(n,0);
if(e->len < npages) {
if(e->next == 0) break;
continue;
}
if(e->len == npages) {
PTE(pn,1)->next = e->next;
return h.pages_off + (n<<OFF_BITS);
}
// note that alternatively we could cutoff block's tail
ne = PTE(n+npages,1);
ne->len = e->len - npages;
ne->next = e->next;
PTE(pn,1)->next = n+npages;
PTE(n,1)->len = npages;
return h.pages_off + (n<<OFF_BITS);
}
return 0; // no suitable block found or ring is empty
}
void ps_free(u8 p) {
Pte *e, *pe;
u8 n, pl;
p = (p - h.pages_off) >> OFF_BITS;
pl = PTE(p,0)->len;
for(n = 0; ; n = e->next) {
e = PTE(n,0);
if(!(n < p && (p+pl <= e->next || !e->next))) continue;
e = PTE(n,1);
if(n+e->len == p) {
e->len += pl;
p = n;
pe = e;
} else {
pe = PTE(p,1);
pe->next = e->next;
e->next = p;
}
if(p+pe->len == pe->next) {
e = PTE(pe->next, 0);
pe->len += e->len;
pe->next = e->next;
}
}
}
#include <string.h>
#include "arc.h"
#include "im.h"
#include "mm.h"
#define ht ((ARC_CDB**)MM(MM_HT_OFF)) /* hash table */
#define cdbt (ARC_CDB*)MM(MM_CD_OFF)
#define frames MM(mm_frames_off)
static ARC_List t1, b1, t2, b2;
// Target length of t1 list:
// increase it, if a hit in the history B1 is observed; similarly,
// decrease it, if a hit in the history B2 is observed.
static int target_t1;
static ARC_CDB *unlink_cdb(ARC_CDB *cdb) {
cdb->list->len--;
cdb->prev->next = cdb->next;
cdb->next->prev = cdb->prev;
return cdb;
}
static ARC_CDB *remove_lru(ARC_List *l) {
return unlink_cdb(l->tail.prev);
}
static void insert_mru(ARC_List *l, ARC_CDB *cdb) {
l->len++;
cdb->list = l;
cdb->prev = &l->head;
cdb->next = cdb->prev->next;
cdb->prev->next = cdb;
cdb->next->prev = cdb;
}
static void ht_insert(ARC_CDB *cdb) {
u4 h = cdb->page%MM_HT_LEN;
cdb->hn = ht[h];
ht[h] = cdb;
}
#if 0
static ARC_CDB *ht_get(u4 page) {
u4 h = page%MM_HT_LEN;
ARC_CDB *p = ht[h];
for( ; p && p->page != page; p = p->hn);
return p;
}
#endif
static void ht_remove(ARC_CDB *cdb) {
u4 h = cdb->page%MM_HT_LEN;
ARC_CDB *p = ht[h], **q = ht+h;
for(;;) {
if(p == cdb) {
*q = p->hn;
return;
}
q = &p->hn;
p = p->hn;
}
}
static void init_list(ARC_List *l) {
l->len = 0;
l->head.prev = 0;
l->tail.next = 0;
l->head.next = &l->tail;
l->tail.prev = &l->head;
}
// finds a frame for incoming page
static u1 *replace() {
ARC_CDB* cdb;
u1 *r;
// T1's size exceeds target?
if(t1.len >= max(1, target_t1)) insert_mru(&b1, cdb = remove_lru(&t1));
else insert_mru(&b2, cdb = remove_lru(&t2));
// if dirty, evict before overwrite
if(cdb->dirty) im_put(cdb->page, cdb->ptr);
mm_clear_tlb_entry(cdb->page);
r = cdb->ptr;
cdb->ptr = 0;
return r;
}
ARC_CDB *arc_get_cdb(u4 page) {
u4 h = page%MM_HT_LEN;
ARC_CDB *a = ht[h];
// try to find the CDB for requested page
for( ; a; a = a->hn) if(a->page == page) {
if(a->ptr) { // hit in cache: t1 or t2
insert_mru(&t2, unlink_cdb(a)); // seen twice, transfer on T2
return a;
}
// else hit in history: b1 or b2
if(a->list == &b1) // adapt the target to favor recency
target_t1 = min(target_t1 + max(b2.len/b1.len, 1), MM_NFRAMES);
else // adapt the target to favor frequency
target_t1 = max(target_t1 - max(b1.len/b2.len, 1), 0);
unlink_cdb(a); // take off whichever list
insert_mru(&t2, a); // seen twice recently, put on T2
a->ptr = replace();
a->page = page;
a->dirty = false;
im_get(a->ptr, a->page); // load page into cache
return a;
}
if(t1.len + b1.len == MM_NFRAMES) { // B1 + T1 full?
if(t1.len < MM_NFRAMES) { // Still room in T1?
a = remove_lru(&b1); // take page off B1
a->ptr = replace();
} else {
a = remove_lru(&t1); // take page off T1
// if dirty, evict before overwrite
if(a->dirty) im_put(a->page, a->ptr);
}
} else { // B1 + T1 have less than c pages
a = remove_lru(&b2); // reuse B2's LRU
a->ptr = replace(); // new place for page
}
ht_remove(a);
insert_mru(&t1, a); // seen once recently, put on T1
a->page = page;
a->dirty = false;
ht_insert(a);
im_get(a->ptr, a->page); // load page into cache
return a;
}
static ARC_CDB *init_cdb(ARC_CDB *cdb, u4 page, bool load_page) {
cdb->page = page;
cdb->dirty = 0;
cdb->ptr = 0;
if(load_page) {
cdb->ptr = frames + page*MM_PAGE_SIZE;
im_get(cdb->ptr, cdb->page);
}
ht_insert(cdb);
return cdb;
}
void arc_init() {
int i;
memset(ht, 0, MM_HT_SIZE);
init_list(&t1);
init_list(&b1);
init_list(&t2);
init_list(&b2);
target_t1 = 1;
for(i = 0; i < MM_NFRAMES; i++)
insert_mru(&t1, init_cdb(cdbt + i, i, true));
for(; i < 2*MM_NFRAMES; i++)
insert_mru(&b2, init_cdb(cdbt + i, i, false));
}
void arc_quit() {
int i;
for(i = 0; i < 2*MM_NFRAMES; i++) {
ARC_CDB *cdb = cdbt + i;
if(cdb->ptr && cdb->dirty)
im_put(cdb->page, cdb->ptr);
}
}