ref: 7b55de41c328b9ec8222ab3a9f2fd407e4ca2c59
dir: /extents.h/
/*
An ordered linked list sorted by block number (->low, ->high).
->big or ->small sorted by size and then block number.
This is similar in functionality to pool(2).
*/
enum
{
Nlru = 32,
};
typedef signed char s8;
typedef signed short s16;
typedef signed int s32;
typedef signed long long s64;
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef struct Extent Extent;
typedef struct Extents Extents;
/*
When allocating blocks from extents:
1. Of all the extents with the len we need, pick the extent with the lowest blkno.
2. If no extent of the len we need is available, then break up the smallest extent.
When freeing blocks, it tries to merge with the neighbours to become bigger extents.
*/
struct Extent {
struct Extent *low, *high; /* sorted by start */
struct Extent *small, *big; /* sorted by the number of blocks in this extent */
u64 start; /* where this extent starts from */
u64 len; /* how many units in this extent */
/* circular least recently used linked list limited to Nlru items */
struct Extent *prev, *next;
};
struct Extents {
char name[32];
u64 quantum; /* allocations are a multiple of quantum */
Extent *lowest; /* find the first block number in a jiffy */
QLock lck;
u64 n; /* number of extents */
Rendez isempty; /* fully used, nothing available */
u8 nlru; /* number of items in the lru linked list */
Extent *lru; /* least recently used extent in the circular lru linked list */
void (*flush)(void);
};
extern int chatty9p;
void *emalloc(u32 sz);
s8 *estrdup(s8 *s);
void panic(char *fmt, ...);
s8 find(Extents *es, u64 bno);
Extent *add(Extents *es, u64 blkno, u64 len);
Extents *holes(Extents *es, Extents *inv);
void showblocknos(int fd, Extents *es);
void showextents(int fd, char *msg, Extents *es);
void showextentslists(int fd, char *msg, Extents *es);
void showextentspointers(int fd, char *msg, Extents *es);
s32 sizeofextents(Extents *es);
s32 saveextents(Extents *es, s8 *buf, u32 nbuf);
s32 loadextents(Extents *es, s8 *buf, u32 nbuf);
u64 balloc(Extents *es, u64 len); /* allocate len*quantum */
void bfree(Extents *es, u64 start, u64 len);/* free len*quantum starting from start */
u64 nfrees(Extents *es);
Extent *lowest(Extents *es);
void initextents(Extents *es, char *name, void (*flush)(void));