Whamcloud - gitweb
ORNL-22 general ptlrpcd threads pool support
[fs/lustre-release.git] / lustre / osd-ldiskfs / osd_iam.h
1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2  * vim:expandtab:shiftwidth=8:tabstop=8:
3  *
4  * GPL HEADER START
5  *
6  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7  *
8  * This program is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License version 2 only,
10  * as published by the Free Software Foundation.
11  *
12  * This program is distributed in the hope that it will be useful, but
13  * WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * General Public License version 2 for more details (a copy is included
16  * in the LICENSE file that accompanied this code).
17  *
18  * You should have received a copy of the GNU General Public License
19  * version 2 along with this program; If not, see [sun.com URL with a
20  * copy of GPLv2].
21  *
22  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23  * CA 95054 USA or visit www.sun.com if you need additional information or
24  * have any questions.
25  *
26  * GPL HEADER END
27  */
28 /*
29  * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
30  * Use is subject to license terms.
31  */
32 /*
33  * This file is part of Lustre, http://www.lustre.org/
34  * Lustre is a trademark of Sun Microsystems, Inc.
35  *
36  * osd_iam.c
37  * Top-level entry points into osd module
38  *
39  * Author: Wang Di <wangdi@clusterfs.com>
40  * Author: Nikita Danilov <nikita@clusterfs.com>
41  */
42
43 #ifndef __LINUX_LUSTRE_IAM_H__
44 #define __LINUX_LUSTRE_IAM_H__
45
46 #include <linux/module.h>
47 #include <asm/unaligned.h>
48 #include <linux/dynlocks.h>
49 /*
50  *  linux/include/linux/osd_iam.h
51  */
52 #ifndef CLASSERT
53 #define CLASSERT(cond) do {switch(42) {case (cond): case 0: break;}} while (0)
54 #endif
55 /* implication */
56 #define ergo(a, b) (!(a) || (b))
57 /* logical equivalence */
58 #define equi(a, b) (!!(a) == !!(b))
59
60 enum {
61         /*
62          * Maximal number of non-leaf levels in htree. In the stock ldiskfs this
63          * is 2.
64          */
65         /*
66          * XXX reduced back to 2 to make per-node locking work.
67          */
68         DX_MAX_TREE_HEIGHT = 5,
69         /*
70          * Scratch keys used by generic code for temporaries.
71          *
72          * Allocation:
73          *
74          *         [0] reserved for assertions and as a staging area for
75          *         record keys immediately used for key comparisons.
76          *
77          *         [1] reserved for record key, stored during iteration over
78          *         node records (see dx_node_check()).
79          *
80          *         [2] reserved for leaf node operations.
81          *
82          *         [3] reserved for index operations.
83          *
84          *         [4] reserved for path->ip_ikey_target
85          *
86          */
87         DX_SCRATCH_KEYS    = 5,
88         /*
89          * Maximal format name length.
90          */
91         DX_FMT_NAME_LEN    = 16,
92 };
93
94 #ifdef __KERNEL__
95
96 /*
97  * Debugging.
98  *
99  * Various debugging levels.
100  */
101
102 #if 0
103 /*
104  * Following macros are defined in config.h and are tunable through
105  * appropriate configure switches (indicated below).
106  */
107
108 /*
109  * Compile basic assertions in. You want this most of the time.
110  *
111  * --{enable,disable}-ldiskfs-assert (on by default).
112  */
113 #define LDISKFS_ASSERT (1)
114
115 /*
116  * Compile heavier correctness checks in. You want this during development
117  * cycle.
118  *
119  * --{enable,disable}-ldiskfs-correctness (off by default).
120  */
121 #define LDISKFS_CORRECTNESS (1)
122
123 /*
124  * Compile heavy invariant checking in. You want this early during development
125  * or when chasing a bug.
126  *
127  * --{enable,disable}-ldiskfs-invariant (off by default).
128  */
129 #define LDISKFS_INVARIANT (1)
130 #endif
131
132 #if defined(LDISKFS_ASSERT)
133 #define LDISKFS_ASSERT_ON (1)
134 #else
135 #define LDISKFS_ASSERT_ON (0)
136 #endif
137
138 #if defined(LDISKFS_CORRECTNESS)
139 #define LDISKFS_CORRECTNESS_ON (1)
140 #else
141 #define LDISKFS_CORRECTNESS_ON (0)
142 #endif
143
144 #if defined(LDISKFS_INVARIANT)
145 #define LDISKFS_INVARIANT_ON (1)
146 #else
147 #define LDISKFS_INVARIANT_ON (0)
148 #endif
149
150 #ifndef assert
151 #if LDISKFS_ASSERT_ON
152 #define assert(test) J_ASSERT(test)
153 #else
154 #define assert(test) ((void)(test))
155 #endif
156 #endif
157
158 #if LDISKFS_CORRECTNESS_ON
159 #define assert_corr(test) J_ASSERT(test)
160 #define do_corr(exp) exp
161 #else
162 #define assert_corr(test) do {;} while (0)
163 #define do_corr(exp) do {;} while (0)
164 #endif
165
166 #if LDISKFS_INVARIANT_ON
167 #define assert_inv(test) J_ASSERT(test)
168 #else
169 #define assert_inv(test) do {;} while (0)
170 #endif
171
172 /*
173  * Entry within index tree node. Consists of a key immediately followed
174  * (without padding) by a pointer to the child node.
175  *
176  * Both key and pointer are of variable size, hence incomplete type.
177  */
178 struct iam_entry;
179
180 struct iam_entry_compat {
181         __le32 hash;
182         __le32 block;
183 };
184
185 /*
186  * Incomplete type used to refer to keys in iam container.
187  *
188  * As key size can be different from container to container, iam has to use
189  * incomplete type. Clients cast pointer to iam_key to real key type and back.
190  */
191 struct iam_key;
192
193 /*
194  * Incomplete type use to refer to the records stored in iam containers.
195  */
196 struct iam_rec;
197
198 /*
199  * Key in index node. Possibly compressed. Fixed size.
200  */
201 struct iam_ikey;
202
203 /*
204  * Scalar type into which certain iam_key's can be uniquely mapped. Used to
205  * support interfaces like readdir(), where iteration over index has to be
206  * re-startable.
207  */
208 typedef __u32 iam_ptr_t;
209
210 /*
211  * Index node traversed during tree lookup.
212  */
213 struct iam_frame {
214         struct buffer_head *bh;    /* buffer holding node data */
215         struct iam_entry *entries; /* array of entries */
216         struct iam_entry *at;      /* target entry, found by binary search */
217         iam_ptr_t         leaf;    /* (logical) offset of child node found by
218                                     * binary search. */
219         iam_ptr_t         curidx;  /* (logical) offset of this node. Used to
220                                     * per-node locking to detect concurrent
221                                     * splits. */
222 };
223
224 /*
225  * Opaque entry in the leaf node.
226  */
227 struct iam_lentry;
228
229 struct iam_path;
230 struct iam_container;
231
232
233 /* leaf node reached by tree lookup */
234 struct iam_leaf {
235         struct iam_path    *il_path;
236         struct buffer_head *il_bh;
237         struct iam_lentry  *il_entries;
238         struct iam_lentry  *il_at;
239         /*
240          * Lock on a leaf node.
241          */
242         struct dynlock_handle *il_lock;
243         iam_ptr_t              il_curidx; /* logical offset of leaf node. */
244         void               *il_descr_data;
245 };
246
247 /*
248  * Return values of ->lookup() operation from struct iam_leaf_operations.
249  */
250 enum iam_lookup_t {
251         /*
252          * lookup found a record with the key requested
253          */
254         IAM_LOOKUP_EXACT  = 0,
255         /*
256          * lookup positioned leaf on some record
257          */
258         IAM_LOOKUP_OK     = 1,
259         /*
260          * leaf was empty
261          */
262         IAM_LOOKUP_EMPTY  = 2,
263         /*
264          * lookup positioned leaf before first record
265          */
266         IAM_LOOKUP_BEFORE = 3,
267         /*
268          * Found hash may have a continuation in the next leaf.
269          */
270         IAM_LOOKUP_LAST   = 0x100
271 };
272
273 /*
274  * Format-specific container operations. These are called by generic iam code.
275  */
276 struct iam_operations {
277         /*
278          * Returns pointer (in the same sense as pointer in index entry) to
279          * the root node.
280          */
281         __u32 (*id_root_ptr)(struct iam_container *c);
282
283         /*
284          * Check validity and consistency of index node.
285          */
286         int (*id_node_check)(struct iam_path *path, struct iam_frame *frame);
287         /*
288          * Copy some data from node header into frame. This is called when
289          * new node is loaded into frame.
290          */
291         int (*id_node_load)(struct iam_path *path, struct iam_frame *frame);
292         /*
293          * Initialize new node (stored in @bh) that is going to be added into
294          * tree.
295          */
296         int (*id_node_init)(struct iam_container *c,
297                             struct buffer_head *bh, int root);
298         int (*id_node_read)(struct iam_container *c, iam_ptr_t ptr,
299                             handle_t *h, struct buffer_head **bh);
300         /*
301          * Key comparison functions. Returns -1, 0, +1.
302          */
303         int (*id_ikeycmp)(const struct iam_container *c,
304                           const struct iam_ikey *k1,
305                           const struct iam_ikey *k2);
306         /*
307          * Modify root node when tree height increases.
308          */
309         struct iam_entry *(*id_root_inc)(struct iam_container *c,
310                                          struct iam_path *path,
311                                          struct iam_frame *frame);
312
313         struct iam_path_descr *(*id_ipd_alloc)(const struct iam_container *c,
314                                                void *area);
315         void (*id_ipd_free)(struct iam_path_descr *ipd);
316         /*
317          * Format name.
318          */
319         char id_name[DX_FMT_NAME_LEN];
320 };
321
322 /*
323  * Another format-specific operation vector, consisting of methods to access
324  * leaf nodes. This is separated from struct iam_operations, because it is
325  * assumed that there will be many formats with different format of leaf
326  * nodes, yes the same struct iam_operations.
327  */
328 struct iam_leaf_operations {
329                 /*
330                  * leaf operations.
331                  */
332
333         /*
334          * initialize just loaded leaf node.
335          */
336         int (*init)(struct iam_leaf *p);
337         /*
338          * Format new node.
339          */
340         void (*init_new)(struct iam_container *c, struct buffer_head *bh);
341         /*
342          * Release resources.
343          */
344         void (*fini)(struct iam_leaf *l);
345                 /*
346                  * returns true iff leaf is positioned at the last entry.
347                  */
348         int (*at_end)(const struct iam_leaf *l);
349                 /* position leaf at the first entry */
350         void (*start)(struct iam_leaf *l);
351                 /* more leaf to the next entry. */
352         void (*next)(struct iam_leaf *l);
353         /*
354          * return key of current leaf record. This method may return
355          * either pointer to the key stored in node, or copy key into
356          * @k buffer supplied by caller and return pointer to this
357          * buffer. The latter approach is used when keys in nodes are
358          * not stored in plain form (e.g., htree doesn't store keys at
359          * all).
360          *
361          * Caller should assume that returned pointer is only valid
362          * while leaf node is pinned and locked.
363          */
364         struct iam_ikey *(*ikey)(const struct iam_leaf *l, struct iam_ikey *k);
365         struct iam_key *(*key)(const struct iam_leaf *l);
366         /* return pointer to entry body. Pointer is valid while
367            corresponding leaf node is locked and pinned. */
368         struct iam_rec *(*rec)(const struct iam_leaf *l);
369
370         void (*key_set)(struct iam_leaf *l, const struct iam_key *k);
371         void (*rec_set)(struct iam_leaf *l, const struct iam_rec *r);
372         void (*rec_get)(const struct iam_leaf *l, struct iam_rec *r);
373
374         int (*key_cmp)(const struct iam_leaf *l, const struct iam_key *k);
375         int (*key_eq)(const struct iam_leaf *l, const struct iam_key *k);
376
377         int (*key_size)(const struct iam_leaf *l);
378         /*
379          * Search leaf @l for a record with key @k or for a place
380          * where such record is to be inserted.
381          *
382          * Scratch keys from @path can be used.
383          */
384         int (*lookup)(struct iam_leaf *l, const struct iam_key *k);
385         int (*ilookup)(struct iam_leaf *l, const struct iam_ikey *ik);
386
387         int (*can_add)(const struct iam_leaf *l,
388                        const struct iam_key *k, const struct iam_rec *r);
389         /*
390          * add rec for a leaf
391          */
392         void (*rec_add)(struct iam_leaf *l,
393                         const struct iam_key *k, const struct iam_rec *r);
394         /*
395          * remove rec for a leaf
396          */
397         void (*rec_del)(struct iam_leaf *l, int shift);
398         /*
399          * split leaf node, moving some entries into @bh (the latter currently
400          * is assumed to be empty).
401          */
402         void (*split)(struct iam_leaf *l, struct buffer_head **bh,
403                       iam_ptr_t newblknr);
404 };
405
406 /*
407  * Parameters, describing a flavor of iam container.
408  */
409 struct iam_descr {
410         /*
411          * Size of a key in this container, in bytes.
412          */
413          size_t       id_key_size;
414         /*
415          * Size of a key in index nodes, in bytes.
416          */
417          size_t       id_ikey_size;
418         /*
419          * Size of a pointer to the next level (stored in index nodes), in
420          * bytes.
421          */
422         size_t       id_ptr_size;
423         /*
424          * Size of a record (stored in leaf nodes), in bytes.
425          */
426         size_t       id_rec_size;
427         /*
428          * Size of unused (by iam) space at the beginning of every non-root
429          * node, in bytes. Used for compatibility with ldiskfs.
430          */
431         size_t       id_node_gap;
432         /*
433          * Size of unused (by iam) space at the beginning of root node, in
434          * bytes. Used for compatibility with ldiskfs.
435          */
436         size_t       id_root_gap;
437
438         struct iam_operations           *id_ops;
439         struct iam_leaf_operations      *id_leaf_ops;
440 };
441
442 /*
443  * An instance of iam container.
444  */
445 struct iam_container {
446         /*
447          * Underlying flat file. IO against this object is issued to
448          * read/write nodes.
449          */
450         struct inode      *ic_object;
451         /*
452          * container flavor.
453          */
454         struct iam_descr  *ic_descr;
455         /*
456          * read-write lock protecting index consistency.
457          */
458         cfs_rw_semaphore_t ic_sem;
459 };
460
461 /*
462  * description-specific part of iam_path. This is usually embedded into larger
463  * structure.
464  */
465 struct iam_path_descr {
466         /*
467          * Scratch-pad area for temporary keys.
468          */
469         struct iam_ikey *ipd_key_scratch[DX_SCRATCH_KEYS];
470 };
471
472 /*
473  * Structure to keep track of a path drilled through htree.
474  */
475 struct iam_path {
476         /*
477          * Parent container.
478          */
479         struct iam_container  *ip_container;
480         /*
481          * Number of index levels minus one.
482          */
483         int                    ip_indirect;
484         /*
485          * Nodes that top-to-bottom traversal passed through.
486          */
487         struct iam_frame       ip_frames[DX_MAX_TREE_HEIGHT];
488         /*
489          * Last filled frame in ->ip_frames. Refers to the 'twig' node (one
490          * immediately above leaf).
491          */
492         struct iam_frame      *ip_frame;
493         /*
494          * Leaf node: a child of ->ip_frame.
495          */
496         struct iam_leaf        ip_leaf;
497         /*
498          * Key searched for.
499          */
500         const struct iam_key  *ip_key_target;
501         const struct iam_ikey *ip_ikey_target;
502         /*
503          * Description-specific data.
504          */
505         struct iam_path_descr *ip_data;
506 };
507
508 struct ldiskfs_dx_hash_info;
509
510 /*
511  * Helper structure for legacy htrees.
512  */
513 struct iam_path_compat {
514         struct iam_path      ipc_path;
515         struct iam_container ipc_container;
516         __u32                 ipc_scratch[DX_SCRATCH_KEYS];
517         struct ldiskfs_dx_hash_info  *ipc_hinfo;
518         struct qstr          *ipc_qstr;
519         struct iam_path_descr ipc_descr;
520         struct ldiskfs_dx_hash_info   ipc_hinfo_area;
521 };
522
523 #define const_max(p, q) ((p > q) ? p : q)
524
525 enum {
526         DX_MAX_IKEY_SIZE   = 32, /* be generous */
527         /*
528          * Hack to avoid dynamic allocation and freeing of ipd.
529          */
530         DX_IPD_MAX_SIZE    = const_max(sizeof(struct iam_path_compat),
531                                        DX_MAX_IKEY_SIZE * DX_SCRATCH_KEYS +
532                                        sizeof(struct iam_path_descr))
533 };
534
535 /*
536  * iam cursor (iterator) api.
537  */
538
539 /*
540  * States of iterator state machine.
541  */
542 enum iam_it_state {
543         /* initial state */
544         IAM_IT_DETACHED,
545         /* iterator is above particular record in the container */
546         IAM_IT_ATTACHED,
547         /* iterator is positioned before record  */
548         IAM_IT_SKEWED
549 };
550
551 /*
552  * Flags controlling iterator functionality.
553  */
554 enum iam_it_flags {
555         /*
556          * this iterator will move (iam_it_next() will be called on it)
557          */
558         IAM_IT_MOVE  = (1 << 0),
559         /*
560          * tree can be updated through this iterator.
561          */
562         IAM_IT_WRITE = (1 << 1)
563 };
564
565 /*
566  * Iterator.
567  *
568  * Immediately after call to iam_it_init() iterator is in "detached"
569  * (IAM_IT_DETACHED) state: it is associated with given parent container, but
570  * doesn't point to any particular record in this container.
571  *
572  * After successful call to iam_it_get() and until corresponding call to
573  * iam_it_put() iterator is in one of "active" states: IAM_IT_ATTACHED or
574  * IAM_IT_SKEWED.
575  *
576  * Active iterator can move through records in a container (provided
577  * IAM_IT_MOVE permission) in a key order, can get record and key values as it
578  * passes over them, and can modify container (provided IAM_IT_WRITE
579  * permission).
580  *
581  * Iteration may reach the end of container, at which point iterator switches
582  * into IAM_IT_DETACHED state.
583  *
584  * Concurrency: iterators are supposed to be local to thread. Interfaces below
585  * do no internal serialization of access to the iterator fields.
586  *
587  * When in non-detached state, iterator keeps some container nodes pinned in
588  * memory and locked (that locking may be implemented at the container
589  * granularity though). In particular, clients may assume that pointers to
590  * records and keys obtained through iterator interface as valid until
591  * iterator is detached (except that they may be invalidated by sub-sequent
592  * operations done through the same iterator).
593  *
594  */
595 struct iam_iterator {
596         /*
597          * iterator flags, taken from enum iam_it_flags.
598          */
599         __u32                 ii_flags;
600         enum iam_it_state     ii_state;
601         /*
602          * path to the record. Valid in IAM_IT_ATTACHED, and IAM_IT_SKEWED
603          * states.
604          */
605         struct iam_path       ii_path;
606 };
607
608 void iam_path_init(struct iam_path *path, struct iam_container *c,
609                    struct iam_path_descr *pd);
610 void iam_path_fini(struct iam_path *path);
611 void iam_path_release(struct iam_path *path);
612
613 void iam_path_compat_init(struct iam_path_compat *path, struct inode *inode);
614 void iam_path_compat_fini(struct iam_path_compat *path);
615
616 struct iam_path_descr *iam_ipd_alloc(void *area, int keysize);
617 void iam_ipd_free(struct iam_path_descr *ipd);
618
619 int  iam_it_init(struct iam_iterator *it, struct iam_container *c, __u32 flags,
620                  struct iam_path_descr *pd);
621 void iam_it_fini(struct iam_iterator *it);
622 int iam_it_get(struct iam_iterator *it, const struct iam_key *k);
623 int iam_it_get_at(struct iam_iterator *it, const struct iam_key *k);
624 void iam_it_dup(struct iam_iterator *dst, const struct iam_iterator *src);
625 void iam_it_put(struct iam_iterator *it);
626 int iam_it_next(struct iam_iterator *it);
627 struct iam_rec *iam_it_rec_get(const struct iam_iterator *it);
628 int iam_it_rec_set(handle_t *h,
629                    struct iam_iterator *it, const struct iam_rec *r);
630 struct iam_key *iam_it_key_get(const struct iam_iterator *it);
631 int iam_it_key_size(const struct iam_iterator *it);
632 int iam_it_rec_insert(handle_t *h, struct iam_iterator *it,
633                       const struct iam_key *k, const struct iam_rec *r);
634 int iam_it_rec_delete(handle_t *h, struct iam_iterator *it);
635
636 typedef __u64 iam_pos_t;
637
638 iam_pos_t iam_it_store(const struct iam_iterator *it);
639 int iam_it_load(struct iam_iterator *it, iam_pos_t pos);
640
641 int iam_lookup(struct iam_container *c, const struct iam_key *k,
642                struct iam_rec *r, struct iam_path_descr *pd);
643 int iam_delete(handle_t *h, struct iam_container *c, const struct iam_key *k,
644                struct iam_path_descr *pd);
645 int iam_update(handle_t *h, struct iam_container *c, const struct iam_key *k,
646                const struct iam_rec *r, struct iam_path_descr *pd);
647 int iam_insert(handle_t *handle, struct iam_container *c,
648                const struct iam_key *k,
649                const struct iam_rec *r, struct iam_path_descr *pd);
650 /*
651  * Initialize container @c.
652  */
653 int iam_container_init(struct iam_container *c,
654                        struct iam_descr *descr, struct inode *inode);
655 /*
656  * Finalize container @c, release all resources.
657  */
658 void iam_container_fini(struct iam_container *c);
659
660 /*
661  * Determine container format.
662  */
663 int iam_container_setup(struct iam_container *c);
664
665 static inline struct iam_descr *iam_container_descr(struct iam_container *c)
666 {
667         return c->ic_descr;
668 }
669
670 static inline struct iam_descr *iam_path_descr(const struct iam_path *p)
671 {
672         return p->ip_container->ic_descr;
673 }
674
675 static inline struct inode *iam_path_obj(struct iam_path *p)
676 {
677         return p->ip_container->ic_object;
678 }
679
680 static inline void iam_ikeycpy(const struct iam_container *c,
681                                struct iam_ikey *k1, const struct iam_ikey *k2)
682 {
683         memcpy(k1, k2, c->ic_descr->id_ikey_size);
684 }
685
686 static inline size_t iam_entry_size(struct iam_path *p)
687 {
688         return iam_path_descr(p)->id_ikey_size + iam_path_descr(p)->id_ptr_size;
689 }
690
691 static inline struct iam_entry *iam_entry_shift(struct iam_path *p,
692                                                 struct iam_entry *entry,
693                                                 int shift)
694 {
695         void *e = entry;
696         return e + shift * iam_entry_size(p);
697 }
698
699 static inline struct iam_ikey *dx_get_ikey(struct iam_path *p,
700                                             struct iam_entry *entry,
701                                             struct iam_ikey *key)
702 {
703         return memcpy(key, entry, iam_path_descr(p)->id_ikey_size);
704 }
705
706 static inline struct iam_ikey *iam_ikey_at(struct iam_path *p,
707                                            struct iam_entry *entry)
708 {
709         return (struct iam_ikey *)entry;
710 }
711
712 static inline ptrdiff_t iam_entry_diff(struct iam_path *p,
713                                        struct iam_entry *e1,
714                                        struct iam_entry *e2)
715 {
716         ptrdiff_t diff;
717
718         diff = (void *)e1 - (void *)e2;
719         assert_corr(diff / iam_entry_size(p) * iam_entry_size(p) == diff);
720         return diff / iam_entry_size(p);
721 }
722
723 /*
724  * Helper for the frequent case, where key was already placed into @k1 by
725  * callback.
726  */
727 static inline void iam_ikeycpy0(const struct iam_container *c,
728                                 struct iam_ikey *k1, const struct iam_ikey *k2)
729 {
730         if (k1 != k2)
731                 iam_ikeycpy(c, k1, k2);
732 }
733
734 static inline int iam_ikeycmp(const struct iam_container *c,
735                               const struct iam_ikey *k1,
736                               const struct iam_ikey *k2)
737 {
738         return c->ic_descr->id_ops->id_ikeycmp(c, k1, k2);
739 }
740
741 static inline void *iam_entry_off(struct iam_entry *entry, size_t off)
742 {
743         return (void *)((char *)entry + off);
744 }
745
746 /*
747  * Leaf helpers.
748  */
749
750 static inline struct iam_path *iam_leaf_path(const struct iam_leaf *leaf)
751 {
752         return leaf->il_path;
753 }
754
755 static inline struct iam_container *
756 iam_leaf_container(const struct iam_leaf *leaf)
757 {
758         return iam_leaf_path(leaf)->ip_container;
759 }
760
761 static inline struct iam_descr *iam_leaf_descr(const struct iam_leaf *leaf)
762 {
763         return iam_leaf_container(leaf)->ic_descr;
764 }
765
766 static inline struct iam_leaf_operations *
767 iam_leaf_ops(const struct iam_leaf *leaf)
768 {
769         return iam_leaf_descr(leaf)->id_leaf_ops;
770 }
771
772 static inline void iam_reccpy(const struct iam_leaf *leaf,
773                               struct iam_rec *rec_dst)
774 {
775         iam_leaf_ops(leaf)->rec_get(leaf, rec_dst);
776 }
777
778 /*XXX These stuff put here, just because they are used by iam.c */
779 static inline unsigned dx_get_block(struct iam_path *p, struct iam_entry *entry)
780 {
781         u32 *addr;
782
783         addr = iam_entry_off(entry, iam_path_descr(p)->id_ikey_size);
784         return le32_to_cpu(get_unaligned(addr));
785 }
786
787 static inline void dx_set_block(struct iam_path *p,
788                                 struct iam_entry *entry, unsigned value)
789 {
790         u32 *addr;
791
792         addr = iam_entry_off(entry, iam_path_descr(p)->id_ikey_size);
793         put_unaligned(cpu_to_le32(value), addr);
794 }
795
796 static inline void dx_set_ikey(struct iam_path *p, struct iam_entry *entry,
797                                const struct iam_ikey *key)
798 {
799         iam_ikeycpy(p->ip_container, iam_entry_off(entry, 0), key);
800 }
801
802 struct dx_map_entry
803 {
804         u32 hash;
805         u32 offs;
806 };
807
808 struct fake_dirent {
809         __le32 inode;
810         __le16 rec_len;
811         u8 name_len;
812         u8 file_type;
813 };
814
815 struct dx_countlimit {
816         __le16 limit;
817         __le16 count;
818 };
819
820 /*
821  * dx_root_info is laid out so that if it should somehow get overlaid by a
822  * dirent the two low bits of the hash version will be zero.  Therefore, the
823  * hash version mod 4 should never be 0.  Sincerely, the paranoia department.
824  */
825
826 struct dx_root {
827         struct fake_dirent dot;
828         char dot_name[4];
829         struct fake_dirent dotdot;
830         char dotdot_name[4];
831         struct dx_root_info
832         {
833                 __le32 reserved_zero;
834                 u8 hash_version;
835                 u8 info_length; /* 8 */
836                 u8 indirect_levels;
837                 u8 unused_flags;
838         }
839         info;
840         struct {} entries[0];
841 };
842
843 struct dx_node
844 {
845         struct fake_dirent fake;
846         struct {} entries[0];
847 };
848
849
850 static inline unsigned dx_get_count(struct iam_entry *entries)
851 {
852         return le16_to_cpu(((struct dx_countlimit *) entries)->count);
853 }
854
855 static inline unsigned dx_get_limit(struct iam_entry *entries)
856 {
857         return le16_to_cpu(((struct dx_countlimit *) entries)->limit);
858 }
859
860 static inline void dx_set_count(struct iam_entry *entries, unsigned value)
861 {
862         ((struct dx_countlimit *) entries)->count = cpu_to_le16(value);
863 }
864
865 static inline unsigned dx_node_limit(struct iam_path *p)
866 {
867         struct iam_descr *param = iam_path_descr(p);
868         unsigned entry_space   = iam_path_obj(p)->i_sb->s_blocksize -
869                 param->id_node_gap;
870         return entry_space / (param->id_ikey_size + param->id_ptr_size);
871 }
872
873 static inline unsigned dx_root_limit(struct iam_path *p)
874 {
875         struct iam_descr *param = iam_path_descr(p);
876         unsigned limit = iam_path_obj(p)->i_sb->s_blocksize -
877                 param->id_root_gap;
878         limit /= (param->id_ikey_size + param->id_ptr_size);
879         if (limit == dx_node_limit(p))
880                 limit--;
881         return limit;
882 }
883
884
885 static inline struct iam_entry *dx_get_entries(struct iam_path *path,
886                                                void *data, int root)
887 {
888         struct iam_descr *param = iam_path_descr(path);
889         return data + (root ? param->id_root_gap : param->id_node_gap);
890 }
891
892
893 static inline struct iam_entry *dx_node_get_entries(struct iam_path *path,
894                                                     struct iam_frame *frame)
895 {
896         return dx_get_entries(path,
897                               frame->bh->b_data, frame == path->ip_frames);
898 }
899
900 static inline struct iam_ikey *iam_path_ikey(const struct iam_path *path,
901                                              int nr)
902 {
903         assert(0 <= nr && nr < ARRAY_SIZE(path->ip_data->ipd_key_scratch));
904         return path->ip_data->ipd_key_scratch[nr];
905 }
906
907
908 static inline struct dynlock *path_dynlock(struct iam_path *path)
909 {
910         return &LDISKFS_I(iam_path_obj(path))->i_htree_lock;
911 }
912
913 static inline int iam_leaf_is_locked(const struct iam_leaf *leaf)
914 {
915         int result;
916
917         result = dynlock_is_locked(path_dynlock(leaf->il_path),
918                                    leaf->il_curidx);
919         if (!result)
920                 dump_stack();
921         return result;
922 }
923
924 static inline int iam_frame_is_locked(struct iam_path *path,
925                                       const struct iam_frame *frame)
926 {
927         int result;
928
929         result = dynlock_is_locked(path_dynlock(path), frame->curidx);
930         if (!result)
931                 dump_stack();
932         return result;
933 }
934
935 int dx_lookup_lock(struct iam_path *path,
936                    struct dynlock_handle **dl, enum dynlock_type lt);
937
938 void dx_insert_block(struct iam_path *path, struct iam_frame *frame,
939                      u32 hash, u32 block);
940 int dx_index_is_compat(struct iam_path *path);
941
942 int ldiskfs_htree_next_block(struct inode *dir, __u32 hash,
943                           struct iam_path *path, __u32 *start_hash);
944
945 struct buffer_head *ldiskfs_append(handle_t *handle, struct inode *inode,
946                                 u32 *block, int *err);
947 int split_index_node(handle_t *handle, struct iam_path *path,
948                      struct dynlock_handle **lh);
949 struct ldiskfs_dir_entry_2 *split_entry(struct inode *dir,
950                                      struct ldiskfs_dir_entry_2 *de,
951                                      unsigned long ino, mode_t mode,
952                                      const char *name, int namelen);
953 struct ldiskfs_dir_entry_2 *find_insertion_point(struct inode *dir,
954                                               struct buffer_head *bh,
955                                               const char *name, int namelen);
956 struct ldiskfs_dir_entry_2 *move_entries(struct inode *dir,
957                                       struct ldiskfs_dx_hash_info *hinfo,
958                                       struct buffer_head **bh1,
959                                       struct buffer_head **bh2,
960                                       __u32 *delim_hash);
961
962 extern struct iam_descr iam_htree_compat_param;
963
964 struct dynlock_handle *dx_lock_htree(struct inode *dir, unsigned long value,
965                                      enum dynlock_type lt);
966 void dx_unlock_htree(struct inode *dir, struct dynlock_handle *lh);
967
968 /*
969  * external
970  */
971 void iam_container_write_lock(struct iam_container *c);
972 void iam_container_write_unlock(struct iam_container *c);
973
974 void iam_container_read_lock(struct iam_container *c);
975 void iam_container_read_unlock(struct iam_container *c);
976
977 int iam_index_next(struct iam_container *c, struct iam_path *p);
978 int iam_read_leaf(struct iam_path *p);
979
980 int iam_node_read(struct iam_container *c, iam_ptr_t ptr,
981                   handle_t *handle, struct buffer_head **bh);
982 int iam_lvar_create(struct inode *obj,
983                     int keysize, int ptrsize, int recsize, handle_t *handle);
984
985 #ifndef swap
986 #define swap(x, y) do { typeof(x) z = x; x = y; y = z; } while (0)
987 #endif
988
989 #ifdef DX_DEBUG
990 #define dxtrace(command) command
991 #else
992 #define dxtrace(command) 
993 #endif
994
995 #define BH_DXLock        25
996 #define DX_DEBUG (0)
997 #if DX_DEBUG
998 static struct iam_lock_stats {
999         unsigned dls_bh_lock;
1000         unsigned dls_bh_busy;
1001         unsigned dls_bh_again;
1002         unsigned dls_bh_full_again;
1003 } iam_lock_stats = { 0, };
1004 #define DX_DEVAL(x) x
1005 #else
1006 #define DX_DEVAL(x)
1007 #endif
1008
1009 static inline void iam_lock_bh(struct buffer_head volatile *bh)
1010 {
1011         DX_DEVAL(iam_lock_stats.dls_bh_lock++);
1012 #ifdef CONFIG_SMP
1013         while (cfs_test_and_set_bit(BH_DXLock, &bh->b_state)) {
1014                 DX_DEVAL(iam_lock_stats.dls_bh_busy++);
1015                 while (cfs_test_bit(BH_DXLock, &bh->b_state))
1016                         cpu_relax();
1017         }
1018 #endif
1019 }
1020
1021 static inline void iam_unlock_bh(struct buffer_head *bh)
1022 {
1023 #ifdef CONFIG_SMP
1024         smp_mb__before_clear_bit();
1025         clear_bit(BH_DXLock, &bh->b_state);
1026 #endif
1027 }
1028
1029
1030 void iam_insert_key(struct iam_path *path, struct iam_frame *frame,
1031                     const struct iam_ikey *key, iam_ptr_t ptr);
1032
1033 void iam_insert_key_lock(struct iam_path *path, struct iam_frame *frame,
1034                          const struct iam_ikey *key, iam_ptr_t ptr);
1035
1036
1037 int  iam_leaf_at_end(const struct iam_leaf *l);
1038 void iam_leaf_next(struct iam_leaf *folio);
1039 int iam_leaf_can_add(const struct iam_leaf *l,
1040                      const struct iam_key *k, const struct iam_rec *r);
1041
1042 struct iam_path *iam_leaf_path(const struct iam_leaf *leaf);
1043 struct iam_container *iam_leaf_container(const struct iam_leaf *leaf);
1044 struct iam_descr *iam_leaf_descr(const struct iam_leaf *leaf);
1045 struct iam_leaf_operations *iam_leaf_ops(const struct iam_leaf *leaf);
1046
1047
1048 int iam_node_read(struct iam_container *c, iam_ptr_t ptr,
1049                   handle_t *h, struct buffer_head **bh);
1050
1051 /*
1052  * Container format.
1053  */
1054 struct iam_format {
1055         /*
1056          * Method called to recognize container format. Should return true iff
1057          * container @c conforms to this format. This method may do IO to read
1058          * container pages.
1059          *
1060          * If container is recognized, this method sets operation vectors
1061          * ->id_ops and ->id_leaf_ops in container description (c->ic_descr),
1062          * and fills other description fields.
1063          */
1064         int (*if_guess)(struct iam_container *c);
1065         /*
1066          * Linkage into global list of container formats.
1067          */
1068         cfs_list_t if_linkage;
1069 };
1070
1071 void iam_format_register(struct iam_format *fmt);
1072 int iam_root_limit(int rootgap, int blocksize, int size);
1073
1074 void iam_lfix_format_init(void);
1075 void iam_lvar_format_init(void);
1076 void iam_htree_format_init(void);
1077
1078 int iam_lfix_create(struct inode *obj,
1079                     int keysize, int ptrsize, int recsize, handle_t *handle);
1080 struct iam_private_info;
1081
1082 void ldiskfs_iam_release(struct file *filp, struct inode *inode);
1083
1084 int iam_uapi_ioctl(struct inode * inode, struct file * filp, unsigned int cmd,
1085                    unsigned long arg);
1086
1087 /* dir.c 
1088 #if LDISKFS_INVARIANT_ON
1089 extern int ldiskfs_check_dir_entry(const char *, struct inode *,
1090                                 struct ldiskfs_dir_entry_2 *,
1091                                 struct buffer_head *, unsigned long);
1092 #else
1093 static inline int ldiskfs_check_dir_entry(const char * function,
1094                                        struct inode * dir,
1095                                        struct ldiskfs_dir_entry_2 * de,
1096                                        struct buffer_head * bh,
1097                                        unsigned long offset)
1098 {
1099         return 1;
1100 }
1101 #endif
1102 */
1103
1104 /* __KERNEL__ */
1105 #endif
1106
1107 /*
1108  * User level API. Copy exists in lustre/lustre/tests/iam_ut.c
1109  */
1110
1111 struct iam_uapi_info {
1112         __u16 iui_keysize;
1113         __u16 iui_recsize;
1114         __u16 iui_ptrsize;
1115         __u16 iui_height;
1116         char  iui_fmt_name[DX_FMT_NAME_LEN];
1117 };
1118
1119 struct iam_uapi_op {
1120         void *iul_key;
1121         void *iul_rec;
1122 };
1123
1124 struct iam_uapi_it {
1125         struct iam_uapi_op iui_op;
1126         __u16              iui_state;
1127 };
1128
1129 enum iam_ioctl_cmd {
1130         IAM_IOC_INIT     = _IOW('i', 1, struct iam_uapi_info),
1131         IAM_IOC_GETINFO  = _IOR('i', 2, struct iam_uapi_info),
1132         IAM_IOC_INSERT   = _IOR('i', 3, struct iam_uapi_op),
1133         IAM_IOC_LOOKUP   = _IOWR('i', 4, struct iam_uapi_op),
1134         IAM_IOC_DELETE   = _IOR('i', 5, struct iam_uapi_op),
1135         IAM_IOC_IT_START = _IOR('i', 6, struct iam_uapi_it),
1136         IAM_IOC_IT_NEXT  = _IOW('i', 7, struct iam_uapi_it),
1137         IAM_IOC_IT_STOP  = _IOR('i', 8, struct iam_uapi_it),
1138
1139         IAM_IOC_POLYMORPH = _IOR('i', 9, unsigned long)
1140 };
1141
1142 /* __LINUX_LUSTRE_IAM_H__ */
1143 #endif