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