HAMMER 7/many - deletions, overwrites, B-Tree work.
[dragonfly.git] / sys / vfs / hammer / hammer_object.c
1 /*
2  * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
3  * 
4  * This code is derived from software contributed to The DragonFly Project
5  * by Matthew Dillon <dillon@backplane.com>
6  * 
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  * 3. Neither the name of The DragonFly Project nor the names of its
18  *    contributors may be used to endorse or promote products derived
19  *    from this software without specific, prior written permission.
20  * 
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  * 
34  * $DragonFly: src/sys/vfs/hammer/hammer_object.c,v 1.6 2007/11/26 21:38:37 dillon Exp $
35  */
36
37 #include "hammer.h"
38
39 static int hammer_mem_add(hammer_transaction_t trans,
40                              hammer_record_t record);
41 static int hammer_mem_lookup(hammer_cursor_t cursor, hammer_inode_t ip);
42 static int hammer_mem_search(hammer_cursor_t cursor, hammer_inode_t ip);
43
44 /*
45  * Red-black tree support.
46  */
47 static int
48 hammer_rec_rb_compare(hammer_record_t rec1, hammer_record_t rec2)
49 {
50         if (rec1->rec.base.base.rec_type < rec2->rec.base.base.rec_type)
51                 return(-1);
52         if (rec1->rec.base.base.rec_type > rec2->rec.base.base.rec_type)
53                 return(1);
54
55         if (rec1->rec.base.base.key < rec2->rec.base.base.key)
56                 return(-1);
57         if (rec1->rec.base.base.key > rec2->rec.base.base.key)
58                 return(1);
59
60         if (rec1->rec.base.base.create_tid < rec2->rec.base.base.create_tid)
61                 return(-1);
62         if (rec1->rec.base.base.create_tid > rec2->rec.base.base.create_tid)
63                 return(1);
64         return(0);
65 }
66
67 static int
68 hammer_rec_compare(hammer_base_elm_t info, hammer_record_t rec)
69 {
70         /*
71          * A key1->rec_type of 0 matches any record type.
72          */
73         if (info->rec_type) {
74                 if (info->rec_type < rec->rec.base.base.rec_type)
75                         return(-3);
76                 if (info->rec_type > rec->rec.base.base.rec_type)
77                         return(3);
78         }
79
80         /*
81          * There is no special case for key.  0 means 0.
82          */
83         if (info->key < rec->rec.base.base.key)
84                 return(-2);
85         if (info->key > rec->rec.base.base.key)
86                 return(2);
87
88         /*
89          * This test has a number of special cases.  create_tid in key1 is
90          * the as-of transction id, and delete_tid in key1 is NOT USED.
91          *
92          * A key1->create_tid of 0 matches any record regardles of when
93          * it was created or destroyed.  0xFFFFFFFFFFFFFFFFULL should be
94          * used to search for the most current state of the object.
95          *
96          * key2->create_tid is a HAMMER record and will never be
97          * 0.   key2->delete_tid is the deletion transaction id or 0 if
98          * the record has not yet been deleted.
99          */
100         if (info->create_tid) {
101                 if (info->create_tid < rec->rec.base.base.create_tid)
102                         return(-1);
103                 if (rec->rec.base.base.delete_tid &&
104                     info->create_tid >= rec->rec.base.base.delete_tid) {
105                         return(1);
106                 }
107         }
108         return(0);
109 }
110
111 /*
112  * RB_SCAN comparison code for hammer_mem_search().  The argument order
113  * is reversed so the comparison result has to be negated.  key_beg and
114  * key_end are both inclusive boundaries.
115  */
116 static
117 int
118 hammer_rec_scan_cmp(hammer_record_t rec, void *data)
119 {
120         hammer_cursor_t cursor = data;
121         int r;
122
123         r = hammer_rec_compare(&cursor->key_beg, rec);
124         if (r > 0)
125                 return(-1);
126         if (r == 0)
127                 return(0);
128         r = hammer_rec_compare(&cursor->key_end, rec);
129         if (r <= 0)
130                 return(1);
131         return(0);
132 }
133
134 RB_GENERATE(hammer_rec_rb_tree, hammer_record, rb_node, hammer_rec_rb_compare);
135 RB_GENERATE_XLOOKUP(hammer_rec_rb_tree, INFO, hammer_record, rb_node,
136                     hammer_rec_compare, hammer_base_elm_t);
137
138 /*
139  * Allocate a record for the caller to finish filling in
140  */
141 hammer_record_t
142 hammer_alloc_mem_record(struct hammer_transaction *trans, hammer_inode_t ip)
143 {
144         hammer_record_t record;
145
146         record = kmalloc(sizeof(*record), M_HAMMER, M_WAITOK|M_ZERO);
147         record->ip = ip;
148         return (record);
149 }
150
151 /*
152  * Release a memory record.  If the record is marked for defered deletion,
153  * destroy the record when the last reference goes away.
154  */
155 void
156 hammer_rel_mem_record(struct hammer_record **recordp)
157 {
158         hammer_record_t rec;
159
160         if ((rec = *recordp) != NULL) {
161                 if (hammer_islastref(&rec->lock)) {
162                         hammer_unref(&rec->lock);
163                         if (rec->flags & HAMMER_RECF_DELETED)
164                                 hammer_free_mem_record(rec);
165                 } else {
166                         hammer_unref(&rec->lock);
167                 }
168                 *recordp = NULL;
169         }
170 }
171
172 /*
173  * Free a record.  Clean the structure up even though we are throwing it
174  * away as a sanity check.  The actual free operation is delayed while
175  * the record is referenced.  However, the record is removed from the RB
176  * tree immediately.
177  */
178 void
179 hammer_free_mem_record(hammer_record_t record)
180 {
181         if (record->flags & HAMMER_RECF_ONRBTREE) {
182                 RB_REMOVE(hammer_rec_rb_tree, &record->ip->rec_tree, record);
183                 record->flags &= ~HAMMER_RECF_ONRBTREE;
184         }
185         if (record->lock.refs) {
186                 record->flags |= HAMMER_RECF_DELETED;
187                 return;
188         }
189         if (record->flags & HAMMER_RECF_ALLOCDATA) {
190                 kfree(record->data, M_HAMMER);
191                 record->flags &= ~HAMMER_RECF_ALLOCDATA;
192         }
193         record->data = NULL;
194         kfree(record, M_HAMMER);
195 }
196
197 /*
198  * Lookup an in-memory record given the key specified in the cursor.  Works
199  * just like hammer_btree_lookup() but operates on an inode's in-memory
200  * record list.
201  *
202  * The lookup must fail if the record is marked for deferred deletion.
203  */
204 static
205 int
206 hammer_mem_lookup(hammer_cursor_t cursor, hammer_inode_t ip)
207 {
208         int error;
209
210         if (cursor->iprec)
211                 hammer_rel_mem_record(&cursor->iprec);
212         if (cursor->ip) {
213                 hammer_rec_rb_tree_scan_info_done(&cursor->scan,
214                                                   &cursor->ip->rec_tree);
215         }
216         cursor->ip = ip;
217         hammer_rec_rb_tree_scan_info_link(&cursor->scan, &ip->rec_tree);
218         cursor->scan.node = NULL;
219         cursor->iprec = hammer_rec_rb_tree_RB_LOOKUP_INFO(
220                                 &ip->rec_tree, &cursor->key_beg);
221         if (cursor->iprec == NULL) {
222                 error = ENOENT;
223         } else {
224                 hammer_ref(&cursor->iprec->lock);
225                 error = 0;
226         }
227         return(error);
228 }
229
230 /*
231  * hammer_mem_search() - locate the first in-memory record matching the
232  * cursor.
233  *
234  * The RB_SCAN function we use is designed as a callback.  We terminate it
235  * (return -1) as soon as we get a match.
236  */
237 static
238 int
239 hammer_rec_scan_callback(hammer_record_t rec, void *data)
240 {
241         hammer_cursor_t cursor = data;
242
243         if (cursor->iprec == NULL) {
244                 cursor->iprec = rec;
245                 hammer_ref(&rec->lock);
246                 return(-1);
247         }
248         return(0);
249 }
250
251 static
252 int
253 hammer_mem_search(hammer_cursor_t cursor, hammer_inode_t ip)
254 {
255         if (cursor->iprec)
256                 hammer_rel_mem_record(&cursor->iprec);
257         if (cursor->ip) {
258                 hammer_rec_rb_tree_scan_info_done(&cursor->scan,
259                                                   &cursor->ip->rec_tree);
260         }
261         cursor->ip = ip;
262         hammer_rec_rb_tree_scan_info_link(&cursor->scan, &ip->rec_tree);
263         cursor->scan.node = NULL;
264         hammer_rec_rb_tree_RB_SCAN(&ip->rec_tree, hammer_rec_scan_cmp,
265                                    hammer_rec_scan_callback, cursor);
266         if (cursor->iprec) {
267                 cursor->scan.node = hammer_rec_rb_tree_RB_NEXT(cursor->iprec);
268                 return(0);
269         }
270         return(ENOENT);
271 }
272
273 void
274 hammer_mem_done(hammer_cursor_t cursor)
275 {
276         if (cursor->ip) {
277                 hammer_rec_rb_tree_scan_info_done(&cursor->scan,
278                                                   &cursor->ip->rec_tree);
279                 cursor->ip = NULL;
280         }
281         if (cursor->iprec)
282                 hammer_rel_mem_record(&cursor->iprec);
283 }
284
285 /************************************************************************
286  *                   HAMMER IN-MEMORY RECORD FUNCTIONS                  *
287  ************************************************************************
288  *
289  * These functions manipulate in-memory records.  Such records typically
290  * exist prior to being committed to disk or indexed via the on-disk B-Tree.
291  */
292
293 /*
294  * Add a directory entry (dip,ncp) which references inode (ip).
295  *
296  * Note that the low 32 bits of the namekey are set temporarily to create
297  * a unique in-memory record, and may be modified a second time when the
298  * record is synchronized to disk.  In particular, the low 32 bits cannot be
299  * all 0's when synching to disk, which is not handled here.
300  */
301 int
302 hammer_ip_add_directory(struct hammer_transaction *trans,
303                      struct hammer_inode *dip, struct namecache *ncp,
304                      struct hammer_inode *ip)
305 {
306         hammer_record_t record;
307         int error;
308         int bytes;
309
310         record = hammer_alloc_mem_record(trans, dip);
311
312         bytes = ncp->nc_nlen;   /* NOTE: terminating \0 is NOT included */
313         if (++trans->hmp->namekey_iterator == 0)
314                 ++trans->hmp->namekey_iterator;
315
316         record->rec.entry.base.base.obj_id = dip->obj_id;
317         record->rec.entry.base.base.key =
318                 hammer_directory_namekey(ncp->nc_name, bytes);
319         record->rec.entry.base.base.key += trans->hmp->namekey_iterator;
320         record->rec.entry.base.base.create_tid = trans->tid;
321         record->rec.entry.base.base.rec_type = HAMMER_RECTYPE_DIRENTRY;
322         record->rec.entry.base.base.obj_type = ip->ino_rec.base.base.obj_type;
323         record->rec.entry.obj_id = ip->obj_id;
324         if (bytes <= sizeof(record->rec.entry.den_name)) {
325                 record->data = (void *)record->rec.entry.den_name;
326                 record->flags |= HAMMER_RECF_EMBEDDED_DATA;
327         } else {
328                 record->data = kmalloc(bytes, M_HAMMER, M_WAITOK);
329                 record->flags |= HAMMER_RECF_ALLOCDATA;
330         }
331         bcopy(ncp->nc_name, record->data, bytes);
332         record->rec.entry.base.data_len = bytes;
333         ++ip->ino_rec.ino_nlinks;
334         hammer_modify_inode(trans, ip,
335                             HAMMER_INODE_RDIRTY | HAMMER_INODE_TID);
336         error = hammer_mem_add(trans, record);
337         return(error);
338 }
339
340 /*
341  * Delete the directory entry and update the inode link count.  The
342  * cursor must be seeked to the directory entry record being deleted.
343  *
344  * NOTE: HAMMER_CURSOR_DELETE may not have been set.  XXX remove flag.
345  */
346 int
347 hammer_ip_del_directory(struct hammer_transaction *trans,
348                      hammer_cursor_t cursor, struct hammer_inode *dip,
349                      struct hammer_inode *ip)
350 {
351         int error;
352
353         if (cursor->record == &cursor->iprec->rec) {
354                 /*
355                  * The directory entry was in-memory, just scrap the
356                  * record.
357                  */
358                 kprintf("del directory mem record\n");
359                 hammer_free_mem_record(cursor->iprec);
360                 error = 0;
361         } else {
362                 /*
363                  * The directory entry was on-disk, mark the record and
364                  * B-Tree entry as deleted.  The B-Tree entry does not
365                  * have to be reindexed because a 'current' delete transid
366                  * will wind up in the same position as the live record.
367                  */
368                 KKASSERT(ip->flags & HAMMER_INODE_ONDISK);
369                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_RECORD);
370                 if (error == 0) {
371                         cursor->node->ondisk->elms[cursor->index].base.delete_tid = trans->tid;
372                         cursor->record->base.base.delete_tid = trans->tid;
373                         hammer_modify_node(cursor->node);
374                         hammer_modify_buffer(cursor->record_buffer);
375                 }
376         }
377
378         /*
379          * One less link.  The file may still be open in the OS even after
380          * all links have gone away so we don't destroy the inode's data
381          * here.
382          */
383         if (error == 0) {
384                 --ip->ino_rec.ino_nlinks;
385                 hammer_modify_inode(trans, ip,
386                                     HAMMER_INODE_RDIRTY | HAMMER_INODE_TID);
387                 if (ip->vp == NULL || (ip->vp->v_flag & VINACTIVE))
388                         hammer_sync_inode(ip, MNT_NOWAIT, 1);
389
390         }
391         return(error);
392 }
393
394 /*
395  * Sync data from a buffer cache buffer (typically) to the filesystem.  This
396  * is called via the strategy called from a cached data source.  This code
397  * is responsible for actually writing a data record out to the disk.
398  */
399 int
400 hammer_ip_sync_data(hammer_transaction_t trans, hammer_inode_t ip,
401                        int64_t offset, void *data, int bytes)
402 {
403         struct hammer_cursor cursor;
404         hammer_record_ondisk_t rec;
405         union hammer_btree_elm elm;
406         void *bdata;
407         int error;
408
409         error = hammer_init_cursor_ip(&cursor, ip);
410         if (error)
411                 return(error);
412         cursor.key_beg.obj_id = ip->obj_id;
413         cursor.key_beg.key = offset + bytes;
414         cursor.key_beg.create_tid = trans->tid;
415         cursor.key_beg.delete_tid = 0;
416         cursor.key_beg.rec_type = HAMMER_RECTYPE_DATA;
417         cursor.flags = HAMMER_CURSOR_INSERT;
418
419         /*
420          * Issue a lookup to position the cursor and locate the cluster
421          */
422         error = hammer_btree_lookup(&cursor);
423         if (error == 0) {
424                 kprintf("hammer_ip_sync_data: duplicate data at (%lld,%d)\n",
425                         offset, bytes);
426                 hammer_print_btree_elm(&cursor.node->ondisk->elms[cursor.index],
427                                        HAMMER_BTREE_TYPE_LEAF, cursor.index);
428                 error = EIO;
429         }
430         if (error != ENOENT)
431                 goto done;
432
433         /*
434          * Allocate record and data space now that we know which cluster
435          * the B-Tree node ended up in.
436          */
437         bdata = hammer_alloc_data(cursor.node->cluster, bytes, &error,
438                                   &cursor.data_buffer);
439         if (bdata == NULL)
440                 goto done;
441         rec = hammer_alloc_record(cursor.node->cluster, &error,
442                                   &cursor.record_buffer);
443         if (rec == NULL)
444                 goto fail1;
445
446         /*
447          * Fill everything in and insert our B-Tree node.
448          */
449         rec->base.base = cursor.key_beg;
450         rec->base.data_crc = crc32(data, bytes);
451         rec->base.rec_id = 0;   /* XXX */
452         rec->base.data_offset = hammer_bclu_offset(cursor.data_buffer, bdata);
453         rec->base.data_len = bytes;
454         hammer_modify_buffer(cursor.record_buffer);
455
456         bcopy(data, bdata, bytes);
457         hammer_modify_buffer(cursor.data_buffer);
458
459         elm.leaf.base = cursor.key_beg;
460         elm.leaf.rec_offset = hammer_bclu_offset(cursor.record_buffer, rec);
461         elm.leaf.data_offset = rec->base.data_offset;
462         elm.leaf.data_len = bytes;
463         elm.leaf.data_crc = rec->base.data_crc;
464
465         error = hammer_btree_insert(&cursor, &elm);
466         if (error == 0)
467                 goto done;
468
469         hammer_free_record_ptr(cursor.record_buffer, rec);
470 fail1:
471         hammer_free_data_ptr(cursor.data_buffer, bdata, bytes);
472 done:
473         hammer_done_cursor(&cursor);
474         return(error);
475 }
476
477 /*
478  * Sync an in-memory record to the disk.  this is typically called via fsync
479  * from a cached record source.  This code is responsible for actually
480  * writing a record out to the disk.
481  */
482 int
483 hammer_ip_sync_record(hammer_record_t record)
484 {
485         struct hammer_cursor cursor;
486         hammer_record_ondisk_t rec;
487         union hammer_btree_elm elm;
488         void *bdata;
489         int error;
490
491         error = hammer_init_cursor_ip(&cursor, record->ip);
492         if (error)
493                 return(error);
494         cursor.key_beg = record->rec.base.base;
495         cursor.flags = HAMMER_CURSOR_INSERT;
496
497         /*
498          * Issue a lookup to position the cursor and locate the cluster
499          */
500         error = hammer_btree_lookup(&cursor);
501         if (error == 0) {
502                 kprintf("hammer_ip_sync_record: duplicate rec at (%016llx)\n",
503                         record->rec.base.base.key);
504                 error = EIO;
505         }
506         if (error != ENOENT)
507                 goto done;
508
509         /*
510          * Allocate record and data space now that we know which cluster
511          * the B-Tree node ended up in.
512          */
513         if (record->data == NULL ||
514             (record->flags & HAMMER_RECF_EMBEDDED_DATA)) {
515                 bdata = record->data;
516         } else {
517                 bdata = hammer_alloc_data(cursor.node->cluster,
518                                           record->rec.base.data_len, &error,
519                                           &cursor.data_buffer);
520                 if (bdata == NULL)
521                         goto done;
522         }
523         rec = hammer_alloc_record(cursor.node->cluster, &error,
524                                   &cursor.record_buffer);
525         if (rec == NULL)
526                 goto fail1;
527
528         /*
529          * Fill everything in and insert our B-Tree node.
530          *
531          * XXX assign rec_id here
532          */
533         *rec = record->rec;
534         if (bdata) {
535                 rec->base.data_crc = crc32(record->data,
536                                            record->rec.base.data_len);
537                 if (record->flags & HAMMER_RECF_EMBEDDED_DATA) {
538                         /*
539                          * Data embedded in record
540                          */
541                         rec->base.data_offset = ((char *)bdata -
542                                                  (char *)&record->rec);
543                         KKASSERT(rec->base.data_offset >= 0 && 
544                                  rec->base.data_offset + rec->base.data_len <
545                                   sizeof(*rec));
546                         rec->base.data_offset += hammer_bclu_offset(cursor.record_buffer, rec);
547                 } else {
548                         /*
549                          * Data separate from record
550                          */
551                         rec->base.data_offset = hammer_bclu_offset(cursor.data_buffer,bdata);
552                         bcopy(record->data, bdata, rec->base.data_len);
553                         hammer_modify_buffer(cursor.data_buffer);
554                 }
555         }
556         rec->base.rec_id = 0;   /* XXX */
557
558         hammer_modify_buffer(cursor.record_buffer);
559
560         elm.leaf.base = cursor.key_beg;
561         elm.leaf.rec_offset = hammer_bclu_offset(cursor.record_buffer, rec);
562         elm.leaf.data_offset = rec->base.data_offset;
563         elm.leaf.data_len = rec->base.data_len;
564         elm.leaf.data_crc = rec->base.data_crc;
565
566         error = hammer_btree_insert(&cursor, &elm);
567         if (error == 0)
568                 goto done;
569
570         hammer_free_record_ptr(cursor.record_buffer, rec);
571 fail1:
572         if (record->data && (record->flags & HAMMER_RECF_EMBEDDED_DATA) == 0) {
573                 hammer_free_data_ptr(cursor.data_buffer, bdata,
574                                      rec->base.data_len);
575         }
576 done:
577         hammer_done_cursor(&cursor);
578         return(error);
579 }
580
581
582 /*
583  * Add the record to the inode's rec_tree.  The low 32 bits of a directory
584  * entry's key is used to deal with hash collisions in the upper 32 bits.
585  * A unique 64 bit key is generated in-memory and may be regenerated a
586  * second time when the directory record is flushed to the on-disk B-Tree.
587  */
588 static
589 int
590 hammer_mem_add(struct hammer_transaction *trans, hammer_record_t record)
591 {
592         while (RB_INSERT(hammer_rec_rb_tree, &record->ip->rec_tree, record)) {
593                 if (record->rec.base.base.rec_type != HAMMER_RECTYPE_DIRENTRY){
594                         hammer_free_mem_record(record);
595                         return (EEXIST);
596                 }
597                 if (++trans->hmp->namekey_iterator == 0)
598                         ++trans->hmp->namekey_iterator;
599                 record->rec.base.base.key &= ~(0xFFFFFFFFLL);
600                 record->rec.base.base.key |= trans->hmp->namekey_iterator;
601         }
602         record->flags |= HAMMER_RECF_ONRBTREE;
603         return(0);
604 }
605
606 /************************************************************************
607  *                   HAMMER INODE MERGED-RECORD FUNCTIONS               *
608  ************************************************************************
609  *
610  * These functions augment the B-Tree scanning functions in hammer_btree.c
611  * by merging in-memory records with on-disk records.
612  */
613
614 /*
615  * Locate a particular record either in-memory or on-disk.
616  *
617  * NOTE: This is basically a standalone routine, hammer_ip_next() may
618  * NOT be called to iterate results.
619  */
620 int
621 hammer_ip_lookup(hammer_cursor_t cursor, struct hammer_inode *ip)
622 {
623         int error;
624
625         /*
626          * If the element is in-memory return it without searching the
627          * on-disk B-Tree
628          */
629         error = hammer_mem_lookup(cursor, ip);
630         if (error == 0) {
631                 cursor->record = &cursor->iprec->rec;
632                 return(error);
633         }
634         if (error != ENOENT)
635                 return(error);
636
637         /*
638          * If the inode has on-disk components search the on-disk B-Tree.
639          */
640         if ((ip->flags & HAMMER_INODE_ONDISK) == 0)
641                 return(error);
642         error = hammer_btree_lookup(cursor);
643         if (error == 0)
644                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_RECORD);
645         return(error);
646 }
647
648 /*
649  * Locate the first record within the cursor's key_beg/key_end range,
650  * restricted to a particular inode.  0 is returned on success, ENOENT
651  * if no records matched the requested range, or some other error.
652  *
653  * When 0 is returned hammer_ip_next() may be used to iterate additional
654  * records within the requested range.
655  */
656 int
657 hammer_ip_first(hammer_cursor_t cursor, struct hammer_inode *ip)
658 {
659         int error;
660
661         /*
662          * Clean up fields and setup for merged scan
663          */
664         cursor->flags |= HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM;
665         cursor->flags |= HAMMER_CURSOR_DISKEOF | HAMMER_CURSOR_MEMEOF;
666         if (cursor->iprec)
667                 hammer_rel_mem_record(&cursor->iprec);
668
669         /*
670          * Search the on-disk B-Tree.  hammer_btree_lookup() only does an
671          * exact lookup so if we get ENOENT we have to call the iterate
672          * function to validate the first record after the begin key.
673          *
674          * The ATEDISK flag is used by hammer_btree_iterate to determine
675          * whether it must index forwards or not.
676          */
677         if (ip->flags & HAMMER_INODE_ONDISK) {
678                 error = hammer_btree_lookup(cursor);
679                 if (error == ENOENT) {
680                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
681                         error = hammer_btree_iterate(cursor);
682                 }
683                 if (error && error != ENOENT) 
684                         return(error);
685                 if (error == 0) {
686                         cursor->flags &= ~HAMMER_CURSOR_DISKEOF;
687                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
688                 } else {
689                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
690                 }
691         }
692
693         /*
694          * Search the in-memory record list (Red-Black tree).  Unlike the
695          * B-Tree search, mem_search checks for records in the range.
696          */
697         error = hammer_mem_search(cursor, ip);
698         if (error && error != ENOENT)
699                 return(error);
700         if (error == 0) {
701                 cursor->flags &= ~HAMMER_CURSOR_MEMEOF;
702                 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
703         }
704
705         /*
706          * This will return the first matching record.
707          */
708         return(hammer_ip_next(cursor));
709 }
710
711 /*
712  * Retrieve the next record in a merged iteration within the bounds of the
713  * cursor.  This call may be made multiple times after the cursor has been
714  * initially searched with hammer_ip_first().
715  *
716  * 0 is returned on success, ENOENT if no further records match the
717  * requested range, or some other error code is returned.
718  */
719 int
720 hammer_ip_next(hammer_cursor_t cursor)
721 {
722         hammer_btree_elm_t elm;
723         hammer_record_t rec;
724         int error;
725         int r;
726
727         /*
728          * Load the current on-disk and in-memory record.  If we ate any
729          * records we have to get the next one. 
730          *
731          * Get the next on-disk record
732          */
733         if (cursor->flags & HAMMER_CURSOR_ATEDISK) {
734                 if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
735                         error = hammer_btree_iterate(cursor);
736                         if (error == 0)
737                                 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
738                         else
739                                 cursor->flags |= HAMMER_CURSOR_DISKEOF;
740                 }
741         }
742
743         /*
744          * Get the next in-memory record.  The record can be ripped out
745          * of the RB tree so we maintain a scan_info structure to track
746          * the next node.
747          */
748         if (cursor->flags & HAMMER_CURSOR_ATEMEM) {
749                 if ((cursor->flags & HAMMER_CURSOR_MEMEOF) == 0) {
750                         rec = cursor->scan.node;        /* next node */
751                         if (rec) {
752                                 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
753                                 hammer_ref(&rec->lock);
754                                 cursor->scan.node =
755                                         hammer_rec_rb_tree_RB_NEXT(rec);
756                         } else {
757                                 cursor->flags |= HAMMER_CURSOR_MEMEOF;
758                         }
759                         hammer_rel_mem_record(&cursor->iprec);
760                         cursor->iprec = rec;
761                 }
762         }
763
764         /*
765          * Extract either the disk or memory record depending on their
766          * relative position.
767          */
768         error = 0;
769         switch(cursor->flags & (HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM)) {
770         case 0:
771                 /*
772                  * Both entries valid
773                  */
774                 elm = &cursor->node->ondisk->elms[cursor->index];
775                 r = hammer_btree_cmp(&elm->base,
776                                      &cursor->iprec->rec.base.base);
777                 if (r < 0) {
778                         error = hammer_btree_extract(cursor,
779                                                      HAMMER_CURSOR_GET_RECORD);
780                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
781                         break;
782                 }
783                 /* fall through to the memory entry */
784         case HAMMER_CURSOR_ATEDISK:
785                 /*
786                  * Only the memory entry is valid
787                  */
788                 cursor->record = &cursor->iprec->rec;
789                 cursor->flags |= HAMMER_CURSOR_ATEMEM;
790                 break;
791         case HAMMER_CURSOR_ATEMEM:
792                 /*
793                  * Only the disk entry is valid
794                  */
795                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_RECORD);
796                 cursor->flags |= HAMMER_CURSOR_ATEDISK;
797                 break;
798         default:
799                 /*
800                  * Neither entry is valid
801                  *
802                  * XXX error not set properly
803                  */
804                 cursor->record = NULL;
805                 error = ENOENT;
806                 break;
807         }
808         return(error);
809 }
810
811 /*
812  * Resolve the cursor->data pointer for the current cursor position in
813  * a merged iteration.
814  */
815 int
816 hammer_ip_resolve_data(hammer_cursor_t cursor)
817 {
818         int error;
819
820         if (cursor->iprec && cursor->record == &cursor->iprec->rec) {
821                 cursor->data = cursor->iprec->data;
822                 error = 0;
823         } else {
824                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_DATA);
825         }
826         return(error);
827 }
828
829 /*
830  * Delete all records within the specified range for inode ip.
831  *
832  * NOTE: An unaligned range will cause new records to be added to cover
833  * the edge cases. (XXX not implemented yet).
834  *
835  * NOTE: ran_end is inclusive (e.g. 0,1023 instead of 0,1024).
836  *
837  * NOTE: Record keys for regular file data have to be special-cased since
838  * they indicate the end of the range (key = base + bytes).
839  */
840 int
841 hammer_ip_delete_range(hammer_transaction_t trans, hammer_inode_t ip,
842                        int64_t ran_beg, int64_t ran_end)
843 {
844         struct hammer_cursor cursor;
845         hammer_record_ondisk_t rec;
846         hammer_base_elm_t base;
847         int error;
848         int isregfile;
849         int64_t off;
850
851         hammer_init_cursor_ip(&cursor, ip);
852
853         cursor.key_beg.obj_id = ip->obj_id;
854         cursor.key_beg.create_tid = ip->obj_asof;
855         cursor.key_beg.delete_tid = 0;
856         cursor.key_beg.obj_type = 0;
857
858         /*
859          * The key in the B-Tree is (base+bytes), so the first possible
860          * matching key is ran_beg + 1.
861          */
862         cursor.key_beg.key = ran_beg + 1;
863         cursor.key_end = cursor.key_beg;
864         if (ip->ino_rec.base.base.obj_type == HAMMER_OBJTYPE_DBFILE) {
865                 cursor.key_beg.rec_type = HAMMER_RECTYPE_DB;
866                 cursor.key_end.rec_type = HAMMER_RECTYPE_DB;
867                 cursor.key_end.key = ran_end;
868                 isregfile = 0;
869         } else {
870                 cursor.key_beg.rec_type = HAMMER_RECTYPE_DATA;
871                 cursor.key_end.rec_type = HAMMER_RECTYPE_DATA;
872                 if (ran_end + MAXPHYS + 1 < ran_end)
873                         cursor.key_end.key = 0x7FFFFFFFFFFFFFFFLL;
874                 else
875                         cursor.key_end.key = ran_end + MAXPHYS + 1;
876                 isregfile = 1;
877         }
878
879         error = hammer_ip_first(&cursor, ip);
880
881         /*
882          * Iterate through matching records and mark them as deleted.
883          */
884         while (error == 0) {
885                 rec = cursor.record;
886                 base = &rec->base.base;
887
888                 KKASSERT(base->delete_tid == 0);
889
890                 /*
891                  * There may be overlap cases for regular file data.  Also
892                  * remember the key for a regular file record is the offset
893                  * of the last byte of the record (base + len - 1), NOT the
894                  * base offset.
895                  */
896                 if (base->rec_type == HAMMER_RECTYPE_DATA) {
897                         off = base->key - rec->base.data_len;
898                         /*
899                          * Check the left edge case.  We currently do not
900                          * split existing records.
901                          */
902                         if (off < ran_beg) {
903                                 panic("hammer left edge case %016llx %d\n",
904                                         base->key, rec->base.data_len);
905                         }
906
907                         /*
908                          * Check the right edge case.  Note that the
909                          * record can be completely out of bounds, which
910                          * terminates the search.
911                          *
912                          * base->key is exclusive of the right edge while
913                          * ran_end is inclusive of the right edge.  The
914                          * (key - data_len) left boundary is inclusive.
915                          */
916                         if (base->key > ran_end + 1) {
917                                 if (base->key - rec->base.data_len > ran_end) {
918                                         kprintf("right edge OOB\n");
919                                         break;
920                                 }
921                                 panic("hammer right edge case\n");
922                         }
923                 }
924
925                 /*
926                  * Mark the record and B-Tree entry as deleted
927                  */
928                 if (cursor.record == &cursor.iprec->rec) {
929                         hammer_free_mem_record(cursor.iprec);
930                 } else {
931                         cursor.node->ondisk->
932                             elms[cursor.index].base.delete_tid = trans->tid;
933                         cursor.record->base.base.delete_tid = trans->tid;
934                         hammer_modify_node(cursor.node);
935                         hammer_modify_buffer(cursor.record_buffer);
936                 }
937                 error = hammer_ip_next(&cursor);
938         }
939         hammer_done_cursor(&cursor);
940         if (error == ENOENT)
941                 error = 0;
942         return(error);
943 }
944