code: libextents

ref: e96b9e14a06a019e20988fa6a80b8871d0db2c44
dir: /extents.h/

View raw version
/*
 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).

 Extents are used to manage contiguous space (such as memory space and disk space).
	The space is is split into units of the same size (quantum).
	The scaling of the addresses (start) by the unit is the responsibility
	of the client.

 All space is split into a sequence of units. Each such sequence of units
	is called an Extent. The data structure Extents is used to contain this
	information. Space is added to the Extents using ufree() and allocated
	using ualloc(). When freed, adjacent extents are coalesced to create a
	large extent, if they are continuous.

 Debugging

	Verbosity induces the dumping of the pool via p->print at each lock operation.
	By default, only one line is logged for each qalloc and qfree.
 */

#pragma lib "libextents.a"
enum
{
	Nlru  = 32,

	/* flags */
	Everbose	= 1,
	Edebug 		= 2,
};

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 Extents {
	char name[32];
	void (*flush)(void);/* flush when nothing is available */
	u8 linger;			/* wait until something becomes available */

	u8 loglevel;	/* Everbose or Edebug */
	u32 logfd;
	int (*log)(int fd, char *fmt, ...);
	void (*panic)(char *fmt, ...);
	void *(*malloc)(u32 sz);	/* as 9p servers use a different malloc */

	/* private and derived */
	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 */
};

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;
};

void	initextents(Extents *es, char *name, u8 linger, u8 loglevel, u32 logfd, void (*flush)(void), int (*log)(int fd, char *fmt, ...), void (*panic)(char *fmt, ...), void *(*malloc)(u32 sz));
void	freeextents(Extents *es);

/* allocate n quanta */
s8	 ualloc(Extents *es, u64 n, u64 *start);
void ufree(Extents *es, u64 start, u64 len);/* free len units starting from start */
u64	 nfrees(Extents *es);
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	sizeoftxtextents(Extents *es);
s32	saveextents(Extents *es, s8 *buf, u32 nbuf);
s32	savetxtextents(Extents *es, s8 *buf, u32 nbuf);
s32	loadextents(Extents *es, s8 *buf, u32 nbuf);