1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
|
/* Virtual Inode management routines
Copyright (C) 2002 Free Software Foundation, Inc.
Written by Marcus Brinkmann.
This file is part of the GNU Hurd.
The GNU Hurd is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
The GNU Hurd is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111, USA. */
/* TODO: Improve NEW by keeping a bitmap of free inodes.
TODO: Improve RLOOKUP by keeping an open hash for keys (need to change
CHANGE and FREE, too).
TODO: Improve FREE by keeping the highest inode in use and keep it
up-to-date. When a table page can be freed, do so. */
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <spin-lock.h>
#include "virt-inode.h"
/* Each virtual inode contains the UNIQUE key it belongs to,
which must not be zero. */
vi_key_t vi_zero_key = {0, 0};
struct v_inode
{
vi_key_t key;
};
/* All inodes are stored in a table by their index number - 1.
Decrementing by one is necessary because inode numbers start from 1,
but our table is zero based. */
#define LOG2_TABLE_PAGE_SIZE 10
#define TABLE_PAGE_SIZE (1 << LOG2_TABLE_PAGE_SIZE)
struct table_page
{
struct table_page *next;
struct v_inode vi[TABLE_PAGE_SIZE];
};
struct table_page *inode_table;
spin_lock_t inode_table_lock = SPIN_LOCK_INITIALIZER;
/* See vi_new and vi_rlookup. */
error_t
_vi_new(vi_key_t key, ino_t *inode, inode_t *v_inode)
{
struct table_page *table = inode_table;
struct table_page *prev_table = 0;
int page = 0;
int offset = 0;
while (table && memcmp(&vi_zero_key, &table->vi[offset].key, sizeof(vi_key_t)))
{
offset++;
if (offset == TABLE_PAGE_SIZE)
{
offset = 0;
page++;
prev_table = table;
table = table->next;
}
}
if (table)
{
table->vi[offset].key = key;
/* See above for rationale of increment. */
*inode = (page << LOG2_TABLE_PAGE_SIZE) + offset + 1;
*v_inode = &table->vi[offset];
}
else
{
struct table_page **pagep;
if (prev_table)
pagep = &prev_table->next;
else
pagep = &inode_table;
*pagep = (struct table_page *) malloc (sizeof (struct table_page));
if (!*pagep)
{
return ENOSPC;
}
memset (*pagep, 0, sizeof (struct table_page));
(*pagep)->vi[0].key = key;
/* See above for rationale of increment. */
*inode = (page << LOG2_TABLE_PAGE_SIZE) + 1;
*v_inode = &(*pagep)->vi[0];
}
return 0;
}
/* Allocate a new inode number INODE for KEY and return it as well as
the virtual inode V_INODE. Return 0 on success, otherwise an error
value (ENOSPC). */
error_t
vi_new(vi_key_t key, ino_t *inode, inode_t *v_inode)
{
error_t err;
assert (memcmp(&vi_zero_key, &key, sizeof (vi_key_t)));
spin_lock (&inode_table_lock);
err = _vi_new(key, inode, v_inode);
spin_unlock (&inode_table_lock);
return err;
}
/* Get the key for virtual inode V_INODE. */
vi_key_t
vi_key(inode_t v_inode)
{
return v_inode->key;
}
/* Get the inode V_INODE belonging to inode number INODE.
Returns 0 if this inode number is free. */
inode_t
vi_lookup(ino_t inode)
{
struct table_page *table = inode_table;
/* See above for rationale of decrement. */
int page = (inode - 1) >> LOG2_TABLE_PAGE_SIZE;
int offset = (inode - 1) & (TABLE_PAGE_SIZE - 1);
inode_t v_inode = 0;
spin_lock (&inode_table_lock);
while (table && page > 0)
{
page--;
table = table->next;
}
if (table)
v_inode = &table->vi[offset];
spin_unlock (&inode_table_lock);
return v_inode;
}
/* Get the inode number and virtual inode belonging to key KEY.
Returns 0 on success and EINVAL if no inode is found for KEY and
CREATE is false. Otherwise, if CREATE is true, allocate new inode. */
error_t
vi_rlookup(vi_key_t key, ino_t *inode, inode_t *v_inode, int create)
{
error_t err = 0;
struct table_page *table = inode_table;
int page = 0;
int offset = 0;
assert (memcmp(&vi_zero_key, &key, sizeof (vi_key_t)));
spin_lock (&inode_table_lock);
while (table && memcmp(&table->vi[offset].key, &key, sizeof (vi_key_t)))
{
offset++;
if (offset == TABLE_PAGE_SIZE)
{
offset = 0;
page++;
table = table->next;
}
}
if (table)
{
/* See above for rationale of increment. */
*inode = (page << LOG2_TABLE_PAGE_SIZE) + offset + 1;
*v_inode = &table->vi[offset];
}
else
{
if (create)
err = _vi_new (key, inode, v_inode);
else
err = EINVAL;
}
spin_unlock (&inode_table_lock);
return err;
}
/* Change the key of virtual inode V_INODE to KEY and return the old
key. */
vi_key_t vi_change(inode_t v_inode, vi_key_t key)
{
vi_key_t okey = v_inode->key;
assert (memcmp(&vi_zero_key, &key, sizeof (vi_key_t)));
v_inode->key = key;
return okey;
}
/* Release virtual inode V_INODE, freeing the inode number. Return
the key. */
vi_key_t vi_free(inode_t v_inode)
{
vi_key_t key;
spin_lock (&inode_table_lock);
key = v_inode->key;
v_inode->key = vi_zero_key;
spin_unlock (&inode_table_lock);
return key;
}
|
