fs/reiser4/plugin/item/item.h

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by reiser4/README */
   2
   3 /* first read balance.c comments before reading this */
   4
   5 /* An item_plugin implements all of the operations required for
   6    balancing that are item specific. */
   7
   8 /* an item plugin also implements other operations that are specific to that
   9    item.  These go into the item specific operations portion of the item
  10    handler, and all of the item specific portions of the item handler are put
  11    into a union. */
  12
  13 #if !defined( __REISER4_ITEM_H__ )
  14 #define __REISER4_ITEM_H__
  15
  16 #include "../../forward.h"
  17 #include "../plugin_header.h"
  18 #include "../../dformat.h"
  19 #include "../../seal.h"
  20 #include "../../plugin/file/file.h"
  21
  22 #include <linux/fs.h>           /* for struct file, struct inode  */
  23 #include <linux/mm.h>           /* for struct page */
  24 #include <linux/dcache.h>       /* for struct dentry */
  25
  26 typedef enum {
  27         STAT_DATA_ITEM_TYPE,
  28         DIR_ENTRY_ITEM_TYPE,
  29         INTERNAL_ITEM_TYPE,
  30         UNIX_FILE_METADATA_ITEM_TYPE,
  31         OTHER_ITEM_TYPE
  32 } item_type_id;
  33
  34 /* this is the part of each item plugin that all items are expected to
  35    support or at least explicitly fail to support by setting the
  36    pointer to null. */
  37 struct balance_ops {
  38         /* operations called by balancing
  39
  40            It is interesting to consider that some of these item
  41            operations could be given sources or targets that are not
  42            really items in nodes.  This could be ok/useful.
  43
  44          */
  45         /* maximal key that can _possibly_ be occupied by this item
  46
  47            When inserting, and node ->lookup() method (called by
  48            coord_by_key()) reaches an item after binary search,
  49            the  ->max_key_inside() item plugin method is used to determine
  50            whether new item should pasted into existing item
  51            (new_key<=max_key_inside()) or new item has to be created
  52            (new_key>max_key_inside()).
  53
  54            For items that occupy exactly one key (like stat-data)
  55            this method should return this key. For items that can
  56            grow indefinitely (extent, directory item) this should
  57            return reiser4_max_key().
  58
  59            For example extent with the key
  60
  61            (LOCALITY,4,OBJID,STARTING-OFFSET), and length BLK blocks,
  62
  63            ->max_key_inside is (LOCALITY,4,OBJID,0xffffffffffffffff), and
  64          */
  65         reiser4_key *(*max_key_inside) (const coord_t *, reiser4_key *);
  66
  67         /* true if item @coord can merge data at @key. */
  68         int (*can_contain_key) (const coord_t *, const reiser4_key *,
  69                                 const reiser4_item_data *);
  70         /* mergeable() - check items for mergeability
  71
  72            Optional method. Returns true if two items can be merged.
  73
  74          */
  75         int (*mergeable) (const coord_t *, const coord_t *);
  76
  77         /* number of atomic things in an item.
  78            NOTE FOR CONTRIBUTORS: use a generic method
  79            nr_units_single_unit() for solid (atomic) items, as
  80            tree operations use it as a criterion of solidness
  81            (see is_solid_item macro) */
  82         pos_in_node_t(*nr_units) (const coord_t *);
  83
  84         /* search within item for a unit within the item, and return a
  85            pointer to it.  This can be used to calculate how many
  86            bytes to shrink an item if you use pointer arithmetic and
  87            compare to the start of the item body if the item's data
  88            are continuous in the node, if the item's data are not
  89            continuous in the node, all sorts of other things are maybe
  90            going to break as well. */
  91          lookup_result(*lookup) (const reiser4_key *, lookup_bias, coord_t *);
  92         /* method called by ode_plugin->create_item() to initialise new
  93            item */
  94         int (*init) (coord_t * target, coord_t * from,
  95                      reiser4_item_data * data);
  96         /* method called (e.g., by reiser4_resize_item()) to place new data
  97            into item when it grows */
  98         int (*paste) (coord_t *, reiser4_item_data *, carry_plugin_info *);
  99         /* return true if paste into @coord is allowed to skip
 100            carry. That is, if such paste would require any changes
 101            at the parent level
 102          */
 103         int (*fast_paste) (const coord_t *);
 104         /* how many but not more than @want units of @source can be
 105            shifted into @target node. If pend == append - we try to
 106            append last item of @target by first units of @source. If
 107            pend == prepend - we try to "prepend" first item in @target
 108            by last units of @source. @target node has @free_space
 109            bytes of free space. Total size of those units are returned
 110            via @size.
 111
 112            @target is not NULL if shifting to the mergeable item and
 113            NULL is new item will be created during shifting.
 114          */
 115         int (*can_shift) (unsigned free_space, coord_t *,
 116                           znode *, shift_direction, unsigned *size,
 117                           unsigned want);
 118
 119         /* starting off @from-th unit of item @source append or
 120            prepend @count units to @target. @target has been already
 121            expanded by @free_space bytes. That must be exactly what is
 122            needed for those items in @target. If @where_is_free_space
 123            == SHIFT_LEFT - free space is at the end of @target item,
 124            othersize - it is in the beginning of it. */
 125         void (*copy_units) (coord_t *, coord_t *,
 126                             unsigned from, unsigned count,
 127                             shift_direction where_is_free_space,
 128                             unsigned free_space);
 129
 130         int (*create_hook) (const coord_t *, void *);
 131         /* do whatever is necessary to do when @count units starting
 132            from @from-th one are removed from the tree */
 133         /* FIXME-VS: this is used to be here for, in particular,
 134            extents and items of internal type to free blocks they point
 135            to at the same time with removing items from a
 136            tree. Problems start, however, when dealloc_block fails due
 137            to some reason. Item gets removed, but blocks it pointed to
 138            are not freed. It is not clear how to fix this for items of
 139            internal type because a need to remove internal item may
 140            appear in the middle of balancing, and there is no way to
 141            undo changes made. OTOH, if space allocator involves
 142            balancing to perform dealloc_block - this will probably
 143            break balancing due to deadlock issues
 144          */
 145         int (*kill_hook) (const coord_t *, pos_in_node_t from,
 146                           pos_in_node_t count, struct carry_kill_data *);
 147         int (*shift_hook) (const coord_t *, unsigned from, unsigned count,
 148                            znode * _node);
 149
 150         /* unit @*from contains @from_key. unit @*to contains @to_key. Cut all keys between @from_key and @to_key
 151            including boundaries. When units are cut from item beginning - move space which gets freed to head of
 152            item. When units are cut from item end - move freed space to item end. When units are cut from the middle of
 153            item - move freed space to item head. Return amount of space which got freed. Save smallest removed key in
 154            @smallest_removed if it is not 0. Save new first item key in @new_first_key if it is not 0
 155          */
 156         int (*cut_units) (coord_t *, pos_in_node_t from, pos_in_node_t to,
 157                           struct carry_cut_data *,
 158                           reiser4_key * smallest_removed,
 159                           reiser4_key * new_first_key);
 160
 161         /* like cut_units, except that these units are removed from the
 162            tree, not only from a node */
 163         int (*kill_units) (coord_t *, pos_in_node_t from, pos_in_node_t to,
 164                            struct carry_kill_data *,
 165                            reiser4_key * smallest_removed,
 166                            reiser4_key * new_first);
 167
 168         /* if @key_of_coord == 1 - returned key of coord, otherwise -
 169            key of unit is returned. If @coord is not set to certain
 170            unit - ERR_PTR(-ENOENT) is returned */
 171         reiser4_key *(*unit_key) (const coord_t *, reiser4_key *);
 172         reiser4_key *(*max_unit_key) (const coord_t *, reiser4_key *);
 173         /* estimate how much space is needed for paste @data into item at
 174            @coord. if @coord==0 - estimate insertion, otherwise - estimate
 175            pasting
 176          */
 177         int (*estimate) (const coord_t *, const reiser4_item_data *);
 178
 179         /* converts flow @f to item data. @coord == 0 on insert */
 180         int (*item_data_by_flow) (const coord_t *, const flow_t *,
 181                                   reiser4_item_data *);
 182
 183         /*void (*show) (struct seq_file *, coord_t *); */
 184
 185 #if REISER4_DEBUG
 186         /* used for debugging, every item should have here the most
 187            complete possible check of the consistency of the item that
 188            the inventor can construct */
 189         int (*check) (const coord_t *, const char **error);
 190 #endif
 191
 192 };
 193
 194 struct flush_ops {
 195         /* return the right or left child of @coord, only if it is in memory */
 196         int (*utmost_child) (const coord_t *, sideof side, jnode ** child);
 197
 198         /* return whether the right or left child of @coord has a non-fake
 199            block number. */
 200         int (*utmost_child_real_block) (const coord_t *, sideof side,
 201                                         reiser4_block_nr *);
 202         /* relocate child at @coord to the @block */
 203         void (*update) (const coord_t *, const reiser4_block_nr *);
 204         /* count unformatted nodes per item for leave relocation policy, etc.. */
 205         int (*scan) (flush_scan * scan);
 206         /* convert item by flush */
 207         int (*convert) (flush_pos_t * pos);
 208         /* backward mapping from jnode offset to a key.  */
 209         int (*key_by_offset) (struct inode *, loff_t, reiser4_key *);
 210 };
 211
 212 /* operations specific to the directory item */
 213 struct dir_entry_iops {
 214         /* extract stat-data key from directory entry at @coord and place it
 215            into @key. */
 216         int (*extract_key) (const coord_t *, reiser4_key * key);
 217         /* update object key in item. */
 218         int (*update_key) (const coord_t *, const reiser4_key *, lock_handle *);
 219         /* extract name from directory entry at @coord and return it */
 220         char *(*extract_name) (const coord_t *, char *buf);
 221         /* extract file type (DT_* stuff) from directory entry at @coord and
 222            return it */
 223         unsigned (*extract_file_type) (const coord_t *);
 224         int (*add_entry) (struct inode * dir,
 225                           coord_t *, lock_handle *,
 226                           const struct dentry * name,
 227                           reiser4_dir_entry_desc * entry);
 228         int (*rem_entry) (struct inode * dir, const struct qstr * name,
 229                           coord_t *, lock_handle *,
 230                           reiser4_dir_entry_desc * entry);
 231         int (*max_name_len) (const struct inode * dir);
 232 };
 233
 234 /* operations specific to items regular (unix) file metadata are built of */
 235 struct file_iops{
 236         int (*write) (struct file *, const char __user *, size_t, loff_t *pos);
 237         int (*read) (struct file *, flow_t *, hint_t *);
 238         int (*readpage) (void *, struct page *);
 239         int (*get_block) (const coord_t *, sector_t, sector_t *);
 240         /*
 241          * key of first byte which is not addressed by the item @coord is set
 242          * to.
 243          * For example, for extent item with the key
 244          *
 245          * (LOCALITY,4,OBJID,STARTING-OFFSET), and length BLK blocks,
 246          *
 247          * ->append_key is
 248          *
 249          * (LOCALITY,4,OBJID,STARTING-OFFSET + BLK * block_size)
 250          */
 251         reiser4_key *(*append_key) (const coord_t *, reiser4_key *);
 252
 253         void (*init_coord_extension) (uf_coord_t *, loff_t);
 254 };
 255
 256 /* operations specific to items of stat data type */
 257 struct sd_iops {
 258         int (*init_inode) (struct inode * inode, char *sd, int len);
 259         int (*save_len) (struct inode * inode);
 260         int (*save) (struct inode * inode, char **area);
 261 };
 262
 263 /* operations specific to internal item */
 264 struct internal_iops{
 265         /* all tree traversal want to know from internal item is where
 266            to go next. */
 267         void (*down_link) (const coord_t * coord,
 268                            const reiser4_key * key, reiser4_block_nr * block);
 269         /* check that given internal item contains given pointer. */
 270         int (*has_pointer_to) (const coord_t * coord,
 271                                const reiser4_block_nr * block);
 272 };
 273
 274 struct item_plugin {
 275         /* generic fields */
 276         plugin_header h;
 277         /* methods common for all item types */
 278         struct balance_ops b; /* balance operations */
 279         struct flush_ops f;   /* flush operates with items via this methods */
 280
 281         /* methods specific to particular type of item */
 282         union {
 283                 struct dir_entry_iops dir;
 284                 struct      file_iops file;
 285                 struct        sd_iops sd;
 286                 struct  internal_iops internal;
 287         } s;
 288 };
 289
 290 #define is_solid_item(iplug) ((iplug)->b.nr_units == nr_units_single_unit)
 291
 292 static inline item_id item_id_by_plugin(item_plugin * plugin)
 293 {
 294         return plugin->h.id;
 295 }
 296
 297 static inline char get_iplugid(item_plugin * iplug)
 298 {
 299         assert("nikita-2838", iplug != NULL);
 300         assert("nikita-2839", iplug->h.id < 0xff);
 301         return (char)item_id_by_plugin(iplug);
 302 }
 303
 304 extern unsigned long znode_times_locked(const znode * z);
 305
 306 static inline void coord_set_iplug(coord_t * coord, item_plugin * iplug)
 307 {
 308         assert("nikita-2837", coord != NULL);
 309         assert("nikita-2838", iplug != NULL);
 310         coord->iplugid = get_iplugid(iplug);
 311         ON_DEBUG(coord->plug_v = znode_times_locked(coord->node));
 312 }
 313
 314 static inline item_plugin *coord_iplug(const coord_t * coord)
 315 {
 316         assert("nikita-2833", coord != NULL);
 317         assert("nikita-2834", coord->iplugid != INVALID_PLUGID);
 318         assert("nikita-3549", coord->plug_v == znode_times_locked(coord->node));
 319         return (item_plugin *) plugin_by_id(REISER4_ITEM_PLUGIN_TYPE,
 320                                             coord->iplugid);
 321 }
 322
 323 extern int item_can_contain_key(const coord_t * item, const reiser4_key * key,
 324                                 const reiser4_item_data *);
 325 extern int are_items_mergeable(const coord_t * i1, const coord_t * i2);
 326 extern int item_is_extent(const coord_t *);
 327 extern int item_is_tail(const coord_t *);
 328 extern int item_is_statdata(const coord_t * item);
 329 extern int item_is_ctail(const coord_t *);
 330
 331 extern pos_in_node_t item_length_by_coord(const coord_t * coord);
 332 extern pos_in_node_t nr_units_single_unit(const coord_t * coord);
 333 extern item_id item_id_by_coord(const coord_t * coord /* coord to query */ );
 334 extern reiser4_key *item_key_by_coord(const coord_t * coord, reiser4_key * key);
 335 extern reiser4_key *max_item_key_by_coord(const coord_t *, reiser4_key *);
 336 extern reiser4_key *unit_key_by_coord(const coord_t * coord, reiser4_key * key);
 337 extern reiser4_key *max_unit_key_by_coord(const coord_t * coord,
 338                                           reiser4_key * key);
 339 extern void obtain_item_plugin(const coord_t * coord);
 340
 341 #if defined(REISER4_DEBUG)
 342 extern int znode_is_loaded(const znode * node);
 343 #endif
 344
 345 /* return plugin of item at @coord */
 346 static inline item_plugin *item_plugin_by_coord(const coord_t *
 347                                                 coord /* coord to query */ )
 348 {
 349         assert("nikita-330", coord != NULL);
 350         assert("nikita-331", coord->node != NULL);
 351         assert("nikita-332", znode_is_loaded(coord->node));
 352
 353         if (unlikely(!coord_is_iplug_set(coord)))
 354                 obtain_item_plugin(coord);
 355         return coord_iplug(coord);
 356 }
 357
 358 /* this returns true if item is of internal type */
 359 static inline int item_is_internal(const coord_t * item)
 360 {
 361         assert("vs-483", coord_is_existing_item(item));
 362         return plugin_of_group(item_plugin_by_coord(item), INTERNAL_ITEM_TYPE);
 363 }
 364
 365 extern void item_body_by_coord_hard(coord_t * coord);
 366 extern void *item_body_by_coord_easy(const coord_t * coord);
 367 #if REISER4_DEBUG
 368 extern int item_body_is_valid(const coord_t * coord);
 369 #endif
 370
 371 /* return pointer to item body */
 372 static inline void *item_body_by_coord(const coord_t *
 373                                        coord /* coord to query */ )
 374 {
 375         assert("nikita-324", coord != NULL);
 376         assert("nikita-325", coord->node != NULL);
 377         assert("nikita-326", znode_is_loaded(coord->node));
 378
 379         if (coord->offset == INVALID_OFFSET)
 380                 item_body_by_coord_hard((coord_t *) coord);
 381         assert("nikita-3201", item_body_is_valid(coord));
 382         assert("nikita-3550", coord->body_v == znode_times_locked(coord->node));
 383         return item_body_by_coord_easy(coord);
 384 }
 385
 386 /* __REISER4_ITEM_H__ */
 387 #endif
 388 /* Make Linus happy.
 389    Local variables:
 390    c-indentation-style: "K&R"
 391    mode-name: "LC"
 392    c-basic-offset: 8
 393    tab-width: 8
 394    fill-column: 120
 395    scroll-step: 1
 396    End:
 397 */