00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #include "tdb_private.h"
00030
00031
00032 int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec)
00033 {
00034 if (tdb->methods->tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1)
00035 return -1;
00036
00037 if (rec->magic == TDB_MAGIC) {
00038
00039
00040 TDB_LOG((tdb, TDB_DEBUG_WARNING, "rec_free_read non-free magic 0x%x at offset=%d - fixing\n",
00041 rec->magic, off));
00042 rec->magic = TDB_FREE_MAGIC;
00043 if (tdb->methods->tdb_write(tdb, off, rec, sizeof(*rec)) == -1)
00044 return -1;
00045 }
00046
00047 if (rec->magic != TDB_FREE_MAGIC) {
00048
00049 tdb->ecode = TDB_ERR_CORRUPT;
00050 TDB_LOG((tdb, TDB_DEBUG_WARNING, "rec_free_read bad magic 0x%x at offset=%d\n",
00051 rec->magic, off));
00052 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
00053 }
00054 if (tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 0) != 0)
00055 return -1;
00056 return 0;
00057 }
00058
00059
00060
00061
00062 static int remove_from_freelist(struct tdb_context *tdb, tdb_off_t off, tdb_off_t next)
00063 {
00064 tdb_off_t last_ptr, i;
00065
00066
00067 last_ptr = FREELIST_TOP;
00068 while (tdb_ofs_read(tdb, last_ptr, &i) != -1 && i != 0) {
00069 if (i == off) {
00070
00071 return tdb_ofs_write(tdb, last_ptr, &next);
00072 }
00073
00074 last_ptr = i;
00075 }
00076 TDB_LOG((tdb, TDB_DEBUG_FATAL,"remove_from_freelist: not on list at off=%d\n", off));
00077 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
00078 }
00079
00080
00081
00082 static int update_tailer(struct tdb_context *tdb, tdb_off_t offset,
00083 const struct list_struct *rec)
00084 {
00085 tdb_off_t totalsize;
00086
00087
00088 totalsize = sizeof(*rec) + rec->rec_len;
00089 return tdb_ofs_write(tdb, offset + totalsize - sizeof(tdb_off_t),
00090 &totalsize);
00091 }
00092
00093
00094
00095 int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec)
00096 {
00097 tdb_off_t right, left;
00098
00099
00100 if (tdb_lock(tdb, -1, F_WRLCK) != 0)
00101 return -1;
00102
00103
00104 if (update_tailer(tdb, offset, rec) != 0) {
00105 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed!\n"));
00106 goto fail;
00107 }
00108
00109
00110 right = offset + sizeof(*rec) + rec->rec_len;
00111 if (right + sizeof(*rec) <= tdb->map_size) {
00112 struct list_struct r;
00113
00114 if (tdb->methods->tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) {
00115 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: right read failed at %u\n", right));
00116 goto left;
00117 }
00118
00119
00120 if (r.magic == TDB_FREE_MAGIC) {
00121 if (remove_from_freelist(tdb, right, r.next) == -1) {
00122 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: right free failed at %u\n", right));
00123 goto left;
00124 }
00125 rec->rec_len += sizeof(r) + r.rec_len;
00126 }
00127 }
00128
00129 left:
00130
00131 left = offset - sizeof(tdb_off_t);
00132 if (left > TDB_DATA_START(tdb->header.hash_size)) {
00133 struct list_struct l;
00134 tdb_off_t leftsize;
00135
00136
00137 if (tdb_ofs_read(tdb, left, &leftsize) == -1) {
00138 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left offset read failed at %u\n", left));
00139 goto update;
00140 }
00141
00142
00143 if (leftsize == 0 || leftsize == TDB_PAD_U32) {
00144 goto update;
00145 }
00146
00147 left = offset - leftsize;
00148
00149
00150 if (tdb->methods->tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) {
00151 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left read failed at %u (%u)\n", left, leftsize));
00152 goto update;
00153 }
00154
00155
00156 if (l.magic == TDB_FREE_MAGIC) {
00157 if (remove_from_freelist(tdb, left, l.next) == -1) {
00158 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left free failed at %u\n", left));
00159 goto update;
00160 } else {
00161 offset = left;
00162 rec->rec_len += leftsize;
00163 }
00164 }
00165 }
00166
00167 update:
00168 if (update_tailer(tdb, offset, rec) == -1) {
00169 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset));
00170 goto fail;
00171 }
00172
00173
00174 rec->magic = TDB_FREE_MAGIC;
00175
00176 if (tdb_ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 ||
00177 tdb_rec_write(tdb, offset, rec) == -1 ||
00178 tdb_ofs_write(tdb, FREELIST_TOP, &offset) == -1) {
00179 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free record write failed at offset=%d\n", offset));
00180 goto fail;
00181 }
00182
00183
00184 tdb_unlock(tdb, -1, F_WRLCK);
00185 return 0;
00186
00187 fail:
00188 tdb_unlock(tdb, -1, F_WRLCK);
00189 return -1;
00190 }
00191
00192
00193
00194
00195
00196
00197 static tdb_off_t tdb_allocate_ofs(struct tdb_context *tdb, tdb_len_t length, tdb_off_t rec_ptr,
00198 struct list_struct *rec, tdb_off_t last_ptr)
00199 {
00200 struct list_struct newrec;
00201 tdb_off_t newrec_ptr;
00202
00203 memset(&newrec, '\0', sizeof(newrec));
00204
00205
00206 if (rec->rec_len > length + MIN_REC_SIZE) {
00207
00208 length = TDB_ALIGN(length, TDB_ALIGNMENT);
00209
00210
00211 newrec.rec_len = rec->rec_len - (sizeof(*rec) + length);
00212 newrec_ptr = rec_ptr + sizeof(*rec) + length;
00213
00214
00215 rec->rec_len = length;
00216 } else {
00217 newrec_ptr = 0;
00218 }
00219
00220
00221 if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1) {
00222 return 0;
00223 }
00224
00225
00226
00227
00228
00229 rec->magic = TDB_MAGIC;
00230 if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
00231 return 0;
00232 }
00233
00234
00235 if (newrec_ptr) {
00236
00237
00238 if (update_tailer(tdb, rec_ptr, rec) == -1) {
00239 return 0;
00240 }
00241
00242
00243 if (tdb_free(tdb, newrec_ptr, &newrec) == -1) {
00244 return 0;
00245 }
00246 }
00247
00248
00249 return rec_ptr;
00250 }
00251
00252
00253
00254
00255
00256
00257
00258 tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_struct *rec)
00259 {
00260 tdb_off_t rec_ptr, last_ptr, newrec_ptr;
00261 struct {
00262 tdb_off_t rec_ptr, last_ptr;
00263 tdb_len_t rec_len;
00264 } bestfit;
00265
00266 if (tdb_lock(tdb, -1, F_WRLCK) == -1)
00267 return 0;
00268
00269
00270 length += sizeof(tdb_off_t);
00271
00272 again:
00273 last_ptr = FREELIST_TOP;
00274
00275
00276 if (tdb_ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
00277 goto fail;
00278
00279 bestfit.rec_ptr = 0;
00280 bestfit.last_ptr = 0;
00281 bestfit.rec_len = 0;
00282
00283
00284
00285
00286
00287
00288 while (rec_ptr) {
00289 if (rec_free_read(tdb, rec_ptr, rec) == -1) {
00290 goto fail;
00291 }
00292
00293 if (rec->rec_len >= length) {
00294 if (bestfit.rec_ptr == 0 ||
00295 rec->rec_len < bestfit.rec_len) {
00296 bestfit.rec_len = rec->rec_len;
00297 bestfit.rec_ptr = rec_ptr;
00298 bestfit.last_ptr = last_ptr;
00299
00300
00301
00302 if (bestfit.rec_len < 2*length) {
00303 break;
00304 }
00305 }
00306 }
00307
00308
00309 last_ptr = rec_ptr;
00310 rec_ptr = rec->next;
00311 }
00312
00313 if (bestfit.rec_ptr != 0) {
00314 if (rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) {
00315 goto fail;
00316 }
00317
00318 newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr, rec, bestfit.last_ptr);
00319 tdb_unlock(tdb, -1, F_WRLCK);
00320 return newrec_ptr;
00321 }
00322
00323
00324
00325 if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
00326 goto again;
00327 fail:
00328 tdb_unlock(tdb, -1, F_WRLCK);
00329 return 0;
00330 }
00331