6 * Copyright (c) 2009-2011, Dan Magenheimer, Oracle Corp.
12 #include <linux/types.h>
13 #include <linux/highmem.h>
14 #include <linux/hash.h>
15 #include <linux/atomic.h>
18 * These are pre-defined by the Xen<->Linux ABI
20 #define TMEM_PUT_PAGE 4
21 #define TMEM_GET_PAGE 5
22 #define TMEM_FLUSH_PAGE 6
23 #define TMEM_FLUSH_OBJECT 7
24 #define TMEM_POOL_PERSIST 1
25 #define TMEM_POOL_SHARED 2
26 #define TMEM_POOL_PRECOMPRESSED 4
27 #define TMEM_POOL_PAGESIZE_SHIFT 4
28 #define TMEM_POOL_PAGESIZE_MASK 0xf
29 #define TMEM_POOL_RESERVED_BITS 0x00ffff00
32 * sentinels have proven very useful for debugging but can be removed
33 * or disabled before final merge.
37 #define DECL_SENTINEL uint32_t sentinel;
38 #define SET_SENTINEL(_x, _y) (_x->sentinel = _y##_SENTINEL)
39 #define INVERT_SENTINEL(_x, _y) (_x->sentinel = ~_y##_SENTINEL)
40 #define ASSERT_SENTINEL(_x, _y) WARN_ON(_x->sentinel != _y##_SENTINEL)
41 #define ASSERT_INVERTED_SENTINEL(_x, _y) WARN_ON(_x->sentinel != ~_y##_SENTINEL)
44 #define SET_SENTINEL(_x, _y) do { } while (0)
45 #define INVERT_SENTINEL(_x, _y) do { } while (0)
46 #define ASSERT_SENTINEL(_x, _y) do { } while (0)
47 #define ASSERT_INVERTED_SENTINEL(_x, _y) do { } while (0)
50 #define ASSERT_SPINLOCK(_l) WARN_ON(!spin_is_locked(_l))
53 * A pool is the highest-level data structure managed by tmem and
54 * usually corresponds to a large independent set of pages such as
55 * a filesystem. Each pool has an id, and certain attributes and counters.
56 * It also contains a set of hash buckets, each of which contains an rbtree
57 * of objects and a lock to manage concurrency within the pool.
60 #define TMEM_HASH_BUCKET_BITS 8
61 #define TMEM_HASH_BUCKETS (1<<TMEM_HASH_BUCKET_BITS)
63 struct tmem_hashbucket
{
64 struct rb_root obj_rb_root
;
69 void *client
; /* "up" for some clients, avoids table lookup */
70 struct list_head pool_list
;
76 struct tmem_hashbucket hashbucket
[TMEM_HASH_BUCKETS
];
80 #define is_persistent(_p) (_p->persistent)
81 #define is_ephemeral(_p) (!(_p->persistent))
84 * An object id ("oid") is large: 192-bits (to ensure, for example, files
85 * in a modern filesystem can be uniquely identified).
92 static inline void tmem_oid_set_invalid(struct tmem_oid
*oidp
)
94 oidp
->oid
[0] = oidp
->oid
[1] = oidp
->oid
[2] = -1UL;
97 static inline bool tmem_oid_valid(struct tmem_oid
*oidp
)
99 return oidp
->oid
[0] != -1UL || oidp
->oid
[1] != -1UL ||
100 oidp
->oid
[2] != -1UL;
103 static inline int tmem_oid_compare(struct tmem_oid
*left
,
104 struct tmem_oid
*right
)
108 if (left
->oid
[2] == right
->oid
[2]) {
109 if (left
->oid
[1] == right
->oid
[1]) {
110 if (left
->oid
[0] == right
->oid
[0])
112 else if (left
->oid
[0] < right
->oid
[0])
116 } else if (left
->oid
[1] < right
->oid
[1])
120 } else if (left
->oid
[2] < right
->oid
[2])
127 static inline unsigned tmem_oid_hash(struct tmem_oid
*oidp
)
129 return hash_long(oidp
->oid
[0] ^ oidp
->oid
[1] ^ oidp
->oid
[2],
130 TMEM_HASH_BUCKET_BITS
);
134 * A tmem_obj contains an identifier (oid), pointers to the parent
135 * pool and the rb_tree to which it belongs, counters, and an ordered
136 * set of pampds, structured in a radix-tree-like tree. The intermediate
137 * nodes of the tree are called tmem_objnodes.
144 struct tmem_pool
*pool
;
145 struct rb_node rb_tree_node
;
146 struct tmem_objnode
*objnode_tree_root
;
147 unsigned int objnode_tree_height
;
148 unsigned long objnode_count
;
153 #define OBJNODE_TREE_MAP_SHIFT 6
154 #define OBJNODE_TREE_MAP_SIZE (1UL << OBJNODE_TREE_MAP_SHIFT)
155 #define OBJNODE_TREE_MAP_MASK (OBJNODE_TREE_MAP_SIZE-1)
156 #define OBJNODE_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
157 #define OBJNODE_TREE_MAX_PATH \
158 (OBJNODE_TREE_INDEX_BITS/OBJNODE_TREE_MAP_SHIFT + 2)
160 struct tmem_objnode
{
161 struct tmem_obj
*obj
;
163 void *slots
[OBJNODE_TREE_MAP_SIZE
];
164 unsigned int slots_in_use
;
167 /* pampd abstract datatype methods provided by the PAM implementation */
169 void *(*create
)(struct tmem_pool
*, struct tmem_oid
*, uint32_t,
171 int (*get_data
)(struct page
*, void *, struct tmem_pool
*);
172 void (*free
)(void *, struct tmem_pool
*);
174 extern void tmem_register_pamops(struct tmem_pamops
*m
);
176 /* memory allocation methods provided by the host implementation */
177 struct tmem_hostops
{
178 struct tmem_obj
*(*obj_alloc
)(struct tmem_pool
*);
179 void (*obj_free
)(struct tmem_obj
*, struct tmem_pool
*);
180 struct tmem_objnode
*(*objnode_alloc
)(struct tmem_pool
*);
181 void (*objnode_free
)(struct tmem_objnode
*, struct tmem_pool
*);
183 extern void tmem_register_hostops(struct tmem_hostops
*m
);
185 /* core tmem accessor functions */
186 extern int tmem_put(struct tmem_pool
*, struct tmem_oid
*, uint32_t index
,
188 extern int tmem_get(struct tmem_pool
*, struct tmem_oid
*, uint32_t index
,
190 extern int tmem_flush_page(struct tmem_pool
*, struct tmem_oid
*,
192 extern int tmem_flush_object(struct tmem_pool
*, struct tmem_oid
*);
193 extern int tmem_destroy_pool(struct tmem_pool
*);
194 extern void tmem_new_pool(struct tmem_pool
*, uint32_t);