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.2 2007/11/19 00:53:40 dillon Exp $ 35 */ 36 37 #include "hammer.h" 38 39 static int hammer_add_record(hammer_transaction_t trans, 40 hammer_record_t record); 41 42 /* 43 * Red-black tree support. 44 */ 45 static int 46 hammer_rec_rb_compare(struct hammer_record *rec1, struct hammer_record *rec2) 47 { 48 if (rec1->rec.base.base.rec_type < rec2->rec.base.base.rec_type) 49 return(-1); 50 if (rec1->rec.base.base.rec_type > rec2->rec.base.base.rec_type) 51 return(1); 52 53 if (rec1->rec.base.base.key < rec2->rec.base.base.key) 54 return(-1); 55 if (rec1->rec.base.base.key > rec2->rec.base.base.key) 56 return(1); 57 58 if (rec1->rec.base.base.create_tid < rec2->rec.base.base.create_tid) 59 return(-1); 60 if (rec1->rec.base.base.create_tid > rec2->rec.base.base.create_tid) 61 return(1); 62 return(0); 63 } 64 65 static int 66 hammer_rec_compare(struct hammer_base_elm *info, struct hammer_record *rec) 67 { 68 /* 69 * A key1->rec_type of 0 matches any record type. 70 */ 71 if (info->rec_type) { 72 if (info->rec_type < rec->rec.base.base.rec_type) 73 return(-3); 74 if (info->rec_type > rec->rec.base.base.rec_type) 75 return(3); 76 } 77 78 /* 79 * There is no special case for key. 0 means 0. 80 */ 81 if (info->key < rec->rec.base.base.key) 82 return(-2); 83 if (info->key > rec->rec.base.base.key) 84 return(2); 85 86 /* 87 * This test has a number of special cases. create_tid in key1 is 88 * the as-of transction id, and delete_tid in key1 is NOT USED. 89 * 90 * A key1->create_tid of 0 matches any record regardles of when 91 * it was created or destroyed. 0xFFFFFFFFFFFFFFFFULL should be 92 * used to search for the most current state of the object. 93 * 94 * key2->create_tid is a HAMMER record and will never be 95 * 0. key2->delete_tid is the deletion transaction id or 0 if 96 * the record has not yet been deleted. 97 */ 98 if (info->create_tid) { 99 if (info->create_tid < rec->rec.base.base.create_tid) 100 return(-1); 101 if (rec->rec.base.base.delete_tid && 102 info->create_tid >= rec->rec.base.base.delete_tid) { 103 return(1); 104 } 105 } 106 return(0); 107 } 108 109 RB_GENERATE(hammer_rec_rb_tree, hammer_record, rb_node, hammer_rec_rb_compare); 110 RB_GENERATE_XLOOKUP(hammer_rec_rb_tree, INFO, hammer_record, rb_node, 111 hammer_rec_compare, hammer_base_elm_t); 112 113 /* 114 * Add a directory entry (dip,ncp) which references inode (ip). 115 * 116 * Note that the low 32 bits of the namekey are set temporarily to create 117 * a unique in-memory record, and may be modified a second time when the 118 * record is synchronized to disk. In particular, the low 32 bits cannot be 119 * all 0's when synching to disk, which is not handled here. 120 */ 121 int 122 hammer_add_directory(struct hammer_transaction *trans, 123 struct hammer_inode *dip, struct namecache *ncp, 124 struct hammer_inode *ip) 125 { 126 struct hammer_record *record; 127 int error; 128 int bytes; 129 130 record = hammer_alloc_ip_record(trans, dip); 131 132 bytes = ncp->nc_nlen + 1; 133 134 record->rec.entry.base.base.obj_id = dip->obj_id; 135 record->rec.entry.base.base.key = hammer_directory_namekey(ncp->nc_name, bytes - 1); 136 record->rec.entry.base.base.key += trans->hmp->namekey_iterator++; 137 record->rec.entry.base.base.create_tid = trans->tid; 138 record->rec.entry.base.base.rec_type = HAMMER_RECTYPE_DIRENTRY; 139 record->rec.entry.base.base.obj_type = ip->ino_rec.base.base.obj_type; 140 record->rec.entry.base.base.obj_id = ip->obj_id; 141 if (bytes <= sizeof(record->rec.entry.den_name)) { 142 record->data = (void *)record->rec.entry.den_name; 143 } else { 144 record->data = kmalloc(bytes, M_HAMMER, M_WAITOK); 145 record->flags |= HAMMER_RECF_ALLOCDATA; 146 bcopy(ncp->nc_name, record->data, bytes); 147 } 148 record->data_len = bytes; 149 ++dip->ino_rec.ino_nlinks; 150 hammer_modify_inode(trans, dip, HAMMER_INODE_RDIRTY); 151 error = hammer_add_record(trans, record); 152 return(error); 153 } 154 155 /* 156 * Allocate a record for the caller to finish filling in 157 */ 158 struct hammer_record * 159 hammer_alloc_ip_record(struct hammer_transaction *trans, hammer_inode_t ip) 160 { 161 hammer_record_t record; 162 163 record = kmalloc(sizeof(*record), M_HAMMER, M_WAITOK|M_ZERO); 164 record->last_tid = trans->tid; 165 record->ip = ip; 166 return (record); 167 } 168 169 /* 170 * Free a record. Clean the structure up even though we are throwing it 171 * away as a sanity check. 172 */ 173 void 174 hammer_free_ip_record(struct hammer_record *record) 175 { 176 if (record->flags & HAMMER_RECF_ONRBTREE) { 177 RB_REMOVE(hammer_rec_rb_tree, &record->ip->rec_tree, record); 178 record->flags &= ~HAMMER_RECF_ONRBTREE; 179 } 180 if (record->flags & HAMMER_RECF_ALLOCDATA) { 181 kfree(record->data, M_HAMMER); 182 record->flags &= ~HAMMER_RECF_ALLOCDATA; 183 } 184 record->data = NULL; 185 kfree(record, M_HAMMER); 186 } 187 188 /* 189 * Add the record to the inode's rec_tree. Directory entries 190 */ 191 static 192 int 193 hammer_add_record(struct hammer_transaction *trans, hammer_record_t record) 194 { 195 while (RB_INSERT(hammer_rec_rb_tree, &record->ip->rec_tree, record)) { 196 if (record->rec.base.base.rec_type != HAMMER_RECTYPE_DIRENTRY){ 197 hammer_free_ip_record(record); 198 return (EEXIST); 199 } 200 record->rec.base.base.key &= ~(0xFFFFFFFFLL); 201 record->rec.base.base.key |= trans->hmp->namekey_iterator++; 202 } 203 record->flags |= HAMMER_RECF_ONRBTREE; 204 return(0); 205 } 206 207 #if 0 208 /* 209 * Delete records belonging to the specified range. Deal with edge and 210 * overlap cases. This function sets the delete tid and breaks adds 211 * up to two records to deal with edge cases, leaving the range as a gap. 212 * The caller will then add records as appropriate. 213 */ 214 int 215 hammer_delete_records(struct hammer_transaction *trans, 216 struct hammer_inode *ip, 217 hammer_base_elm_t ran_beg, hammer_base_elm_t ran_end) 218 { 219 } 220 221 #endif 222