Skip to content

Commit d1698fc

Browse files
kvapkvap
committed
Move blockmem implementation out of the main raftable module.
1 parent d7f5052 commit d1698fc

File tree

4 files changed

+272
-0
lines changed

4 files changed

+272
-0
lines changed

‎contrib/raftable/blockmem.c

Lines changed: 168 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,168 @@
1+
#include "blockmem.h"
2+
3+
#include <stddef.h>
4+
#include <assert.h>
5+
#include <stdbool.h>
6+
#include <string.h>
7+
8+
#define BLOCK_LEN (256)
9+
#define BLOCK_DATA_LEN ((BLOCK_LEN) - offsetof(block_t, data))
10+
#define META(ORIGIN) ((meta_t *)(ORIGIN))
11+
#define BLOCK(ORIGIN, ID) ((block_t *)((char *)(ORIGIN) + BLOCK_LEN * ID))
12+
#define TAIL(ORIGIN, ID) (BLOCK(ORIGIN, ID)->next)
13+
#define USED(ORIGIN, ID) (BLOCK(ORIGIN, ID)->used)
14+
#define LEN(ORIGIN, ID) (BLOCK(ORIGIN, ID)->len)
15+
#define DATA(ORIGIN, ID) (BLOCK(ORIGIN, ID)->data)
16+
#define FREE(ORIGIN) (META(ORIGIN)->freeblock)
17+
18+
typedef struct meta_t
19+
{
20+
int freeblock; /* the id of first free block, or -1 if none */
21+
char data[1];
22+
} meta_t;
23+
24+
typedef struct block_t
25+
{
26+
bool used;
27+
int next;
28+
int len;
29+
char data[1];
30+
} block_t;
31+
32+
int
33+
blockmem_format(void *origin, size_t size)
34+
{
35+
block_t *block;
36+
meta_t *meta;
37+
int id;
38+
int blocks = (size - 1) / BLOCK_LEN;
39+
if (blocks <= 0) return 0;
40+
41+
FREE(origin) = 1;
42+
43+
for (id = 1; id <= blocks; id++)
44+
{
45+
USED(origin, id) = 0;
46+
TAIL(origin, id) = id + 1;
47+
}
48+
TAIL(origin, blocks) = 0; /* the last block has no tail */
49+
50+
return 1;
51+
}
52+
53+
static size_t
54+
block_fill(void *origin, int id, void *src, size_t len)
55+
{
56+
if (len > BLOCK_DATA_LEN)
57+
len = BLOCK_DATA_LEN;
58+
LEN(origin, id) = len;
59+
memcpy(DATA(origin, id), src, len);
60+
return len;
61+
}
62+
63+
void
64+
block_clear(void *origin, int id)
65+
{
66+
TAIL(origin, id) = 0;
67+
USED(origin, id) = true;
68+
LEN(origin, id) = 0;
69+
}
70+
71+
static int
72+
block_alloc(void *origin)
73+
{
74+
int newborn = FREE(origin);
75+
if (!newborn) return 0;
76+
77+
FREE(origin) = TAIL(origin, newborn);
78+
block_clear(origin, newborn);
79+
return newborn;
80+
}
81+
82+
static void
83+
block_free(void *origin, int id)
84+
{
85+
/* behead the victim, and repeat for the tail */
86+
while (id > 0)
87+
{
88+
int tail;
89+
assert(USED(origin, id));
90+
91+
USED(origin, id) = false;
92+
tail = TAIL(origin, id);
93+
TAIL(origin, id) = FREE(origin);
94+
FREE(origin) = id;
95+
id = tail;
96+
}
97+
}
98+
99+
int
100+
blockmem_put(void *origin, void *src, size_t len)
101+
{
102+
int head = 0;
103+
int id = 0;
104+
char *cursor = src;
105+
size_t bytesleft = len;
106+
107+
while (bytesleft > 0)
108+
{
109+
int copied;
110+
int newid = block_alloc(origin);
111+
if (!newid) goto failure;
112+
113+
copied = block_fill(origin, newid, cursor, bytesleft);
114+
115+
cursor += copied;
116+
bytesleft -= copied;
117+
if (id)
118+
TAIL(origin, id) = newid;
119+
else
120+
head = newid;
121+
id = newid;
122+
}
123+
124+
return head;
125+
failure:
126+
block_free(origin, head);
127+
return -1;
128+
}
129+
130+
size_t
131+
blockmem_len(void *origin, int id)
132+
{
133+
size_t len = 0;
134+
while (id > 0)
135+
{
136+
assert(USED(origin, id));
137+
len += LEN(origin, id);
138+
id = TAIL(origin, id);
139+
}
140+
assert(len > 0);
141+
return len;
142+
}
143+
144+
size_t
145+
blockmem_get(void *origin, int id, void *dst, size_t len)
146+
{
147+
size_t copied = 0;
148+
char *cursor = dst;
149+
while ((id > 0) && (copied < len))
150+
{
151+
size_t tocopy = LEN(origin, id);
152+
if (tocopy > len - copied)
153+
tocopy = len - copied;
154+
assert(tocopy > 0);
155+
assert(USED(origin, id));
156+
memcpy(cursor, DATA(origin, id), tocopy);
157+
copied += tocopy;
158+
cursor += tocopy;
159+
id = TAIL(origin, id);
160+
}
161+
return len;
162+
}
163+
164+
void
165+
blockmem_forget(void *origin, int id)
166+
{
167+
block_free(origin, id);
168+
}

‎contrib/raftable/blockmem.h

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
#ifndef BLOCKMEM_H
2+
#define BLOCKMEM_H
3+
4+
#include <stdlib.h>
5+
6+
/*
7+
* Formats the memory region of 'size' bytes starting at 'origin'. Use this
8+
* before any other functions related to blockmem. Returns 1 on success,
9+
* 0 otherwise.
10+
*/
11+
int blockmem_format(void *origin, size_t size);
12+
13+
/*
14+
* Allocates blocks in the formatted region starting at 'origin' and stores
15+
* 'len' bytes from 'src' inside those blocks. Returns the id for later _get(),
16+
* _len() and _forget() operations. Returns 0 if not enough free blocks.
17+
*/
18+
int blockmem_put(void *origin, void *src, size_t len);
19+
20+
/*
21+
* Returns the length of data identified by 'id' that was previously stored
22+
* with a call to _put().
23+
*/
24+
size_t blockmem_len(void *origin, int id);
25+
26+
/*
27+
* Retrieves into 'dst' no more than 'len' bytes of data identified by 'id'
28+
* that were previously stored with a call to _put(). Returns the length of data
29+
* actually copied.
30+
*/
31+
size_t blockmem_get(void *origin, int id, void *dst, size_t len);
32+
33+
/*
34+
* Frees the blocks occupied by data identified by 'id'.
35+
*/
36+
void blockmem_forget(void *origin, int id);
37+
38+
#endif

‎contrib/raftable/test-blockmem.c

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
#include <stdio.h>
2+
#include <stdlib.h>
3+
#include <string.h>
4+
5+
#include "blockmem.h"
6+
7+
#define BLOCKMEM_SIZE (1024 * 1024)
8+
#define TEST_SIZE (10000)
9+
10+
int
11+
main()
12+
{
13+
int rc = EXIT_SUCCESS;
14+
void *origin = malloc(BLOCKMEM_SIZE);
15+
if (!blockmem_format(origin, BLOCKMEM_SIZE))
16+
{
17+
fprintf(stderr, "couldn't format the blockmem\n");
18+
rc = EXIT_FAILURE;
19+
}
20+
else
21+
{
22+
char *a, *b;
23+
int i, id;
24+
25+
a = malloc(TEST_SIZE);
26+
b = malloc(TEST_SIZE);
27+
28+
for (i = 0; i < TEST_SIZE; i++)
29+
{
30+
a[i] = rand() % ('z' - 'a' + 1) + 'a';
31+
b[i] = '\0';
32+
}
33+
a[TEST_SIZE - 1] = '\0';
34+
35+
id = blockmem_put(origin, a, TEST_SIZE);
36+
i = blockmem_get(origin, id, b, TEST_SIZE);
37+
if (i != TEST_SIZE)
38+
{
39+
fprintf(stderr, "got %d instead of %d\n", i, TEST_SIZE);
40+
rc = EXIT_FAILURE;
41+
}
42+
43+
if (strcmp(a, b))
44+
{
45+
fprintf(stderr, "did not get out what was put in\n");
46+
rc = EXIT_FAILURE;
47+
}
48+
49+
free(b);
50+
free(a);
51+
52+
free(origin);
53+
}
54+
55+
if (rc == EXIT_SUCCESS)
56+
fprintf(stderr, "blockmem test ok\n");
57+
else
58+
fprintf(stderr, "blockmem test failed\n");
59+
60+
return rc;
61+
}

‎contrib/raftable/test.sh

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
#!/bin/sh
2+
CC=clang
3+
set -ex
4+
$CC -o test-blockmem test-blockmem.c blockmem.c
5+
./test-blockmem

0 commit comments

Comments
 (0)