regmap: rbtree: Factor out node allocation
[deliverable/linux.git] / drivers / base / regmap / regcache-rbtree.c
CommitLineData
28644c80
DP
1/*
2 * Register cache access API - rbtree caching support
3 *
4 * Copyright 2011 Wolfson Microelectronics plc
5 *
6 * Author: Dimitris Papastamos <dp@opensource.wolfsonmicro.com>
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 as
10 * published by the Free Software Foundation.
11 */
12
13#include <linux/slab.h>
51990e82 14#include <linux/device.h>
bad2ab4b 15#include <linux/debugfs.h>
28644c80 16#include <linux/rbtree.h>
bad2ab4b 17#include <linux/seq_file.h>
28644c80
DP
18
19#include "internal.h"
20
21static int regcache_rbtree_write(struct regmap *map, unsigned int reg,
22 unsigned int value);
462a185c 23static int regcache_rbtree_exit(struct regmap *map);
28644c80
DP
24
25struct regcache_rbtree_node {
26 /* the actual rbtree node holding this block */
27 struct rb_node node;
28 /* base register handled by this block */
29 unsigned int base_reg;
28644c80
DP
30 /* block of adjacent registers */
31 void *block;
32 /* number of registers available in the block */
33 unsigned int blklen;
34} __attribute__ ((packed));
35
36struct regcache_rbtree_ctx {
37 struct rb_root root;
38 struct regcache_rbtree_node *cached_rbnode;
39};
40
41static inline void regcache_rbtree_get_base_top_reg(
f01ee60f 42 struct regmap *map,
28644c80
DP
43 struct regcache_rbtree_node *rbnode,
44 unsigned int *base, unsigned int *top)
45{
46 *base = rbnode->base_reg;
f01ee60f 47 *top = rbnode->base_reg + ((rbnode->blklen - 1) * map->reg_stride);
28644c80
DP
48}
49
879082c9
MB
50static unsigned int regcache_rbtree_get_register(struct regmap *map,
51 struct regcache_rbtree_node *rbnode, unsigned int idx)
28644c80 52{
879082c9 53 return regcache_get_val(map, rbnode->block, idx);
28644c80
DP
54}
55
879082c9
MB
56static void regcache_rbtree_set_register(struct regmap *map,
57 struct regcache_rbtree_node *rbnode,
58 unsigned int idx, unsigned int val)
28644c80 59{
879082c9 60 regcache_set_val(map, rbnode->block, idx, val);
28644c80
DP
61}
62
3405addd 63static struct regcache_rbtree_node *regcache_rbtree_lookup(struct regmap *map,
879082c9 64 unsigned int reg)
28644c80 65{
3405addd 66 struct regcache_rbtree_ctx *rbtree_ctx = map->cache;
28644c80
DP
67 struct rb_node *node;
68 struct regcache_rbtree_node *rbnode;
69 unsigned int base_reg, top_reg;
70
3405addd
LPC
71 rbnode = rbtree_ctx->cached_rbnode;
72 if (rbnode) {
f01ee60f
SW
73 regcache_rbtree_get_base_top_reg(map, rbnode, &base_reg,
74 &top_reg);
3405addd
LPC
75 if (reg >= base_reg && reg <= top_reg)
76 return rbnode;
77 }
78
79 node = rbtree_ctx->root.rb_node;
28644c80
DP
80 while (node) {
81 rbnode = container_of(node, struct regcache_rbtree_node, node);
f01ee60f
SW
82 regcache_rbtree_get_base_top_reg(map, rbnode, &base_reg,
83 &top_reg);
3405addd
LPC
84 if (reg >= base_reg && reg <= top_reg) {
85 rbtree_ctx->cached_rbnode = rbnode;
28644c80 86 return rbnode;
3405addd 87 } else if (reg > top_reg) {
28644c80 88 node = node->rb_right;
3405addd 89 } else if (reg < base_reg) {
28644c80 90 node = node->rb_left;
3405addd 91 }
28644c80
DP
92 }
93
94 return NULL;
95}
96
f01ee60f 97static int regcache_rbtree_insert(struct regmap *map, struct rb_root *root,
28644c80
DP
98 struct regcache_rbtree_node *rbnode)
99{
100 struct rb_node **new, *parent;
101 struct regcache_rbtree_node *rbnode_tmp;
102 unsigned int base_reg_tmp, top_reg_tmp;
103 unsigned int base_reg;
104
105 parent = NULL;
106 new = &root->rb_node;
107 while (*new) {
108 rbnode_tmp = container_of(*new, struct regcache_rbtree_node,
109 node);
110 /* base and top registers of the current rbnode */
f01ee60f 111 regcache_rbtree_get_base_top_reg(map, rbnode_tmp, &base_reg_tmp,
28644c80
DP
112 &top_reg_tmp);
113 /* base register of the rbnode to be added */
114 base_reg = rbnode->base_reg;
115 parent = *new;
116 /* if this register has already been inserted, just return */
117 if (base_reg >= base_reg_tmp &&
118 base_reg <= top_reg_tmp)
119 return 0;
120 else if (base_reg > top_reg_tmp)
121 new = &((*new)->rb_right);
122 else if (base_reg < base_reg_tmp)
123 new = &((*new)->rb_left);
124 }
125
126 /* insert the node into the rbtree */
127 rb_link_node(&rbnode->node, parent, new);
128 rb_insert_color(&rbnode->node, root);
129
130 return 1;
131}
132
bad2ab4b
MB
133#ifdef CONFIG_DEBUG_FS
134static int rbtree_show(struct seq_file *s, void *ignored)
135{
136 struct regmap *map = s->private;
137 struct regcache_rbtree_ctx *rbtree_ctx = map->cache;
138 struct regcache_rbtree_node *n;
139 struct rb_node *node;
140 unsigned int base, top;
a42277c7 141 size_t mem_size;
bad2ab4b
MB
142 int nodes = 0;
143 int registers = 0;
f01ee60f 144 int this_registers, average;
bad2ab4b 145
bacdbe07 146 map->lock(map);
bad2ab4b 147
a42277c7 148 mem_size = sizeof(*rbtree_ctx);
78493f2d 149 mem_size += BITS_TO_LONGS(map->cache_present_nbits) * sizeof(long);
a42277c7 150
bad2ab4b
MB
151 for (node = rb_first(&rbtree_ctx->root); node != NULL;
152 node = rb_next(node)) {
153 n = container_of(node, struct regcache_rbtree_node, node);
a42277c7
DP
154 mem_size += sizeof(*n);
155 mem_size += (n->blklen * map->cache_word_size);
bad2ab4b 156
f01ee60f
SW
157 regcache_rbtree_get_base_top_reg(map, n, &base, &top);
158 this_registers = ((top - base) / map->reg_stride) + 1;
159 seq_printf(s, "%x-%x (%d)\n", base, top, this_registers);
bad2ab4b
MB
160
161 nodes++;
f01ee60f 162 registers += this_registers;
bad2ab4b
MB
163 }
164
c04c1b9e
SW
165 if (nodes)
166 average = registers / nodes;
167 else
168 average = 0;
169
a42277c7
DP
170 seq_printf(s, "%d nodes, %d registers, average %d registers, used %zu bytes\n",
171 nodes, registers, average, mem_size);
bad2ab4b 172
bacdbe07 173 map->unlock(map);
bad2ab4b
MB
174
175 return 0;
176}
177
178static int rbtree_open(struct inode *inode, struct file *file)
179{
180 return single_open(file, rbtree_show, inode->i_private);
181}
182
183static const struct file_operations rbtree_fops = {
184 .open = rbtree_open,
185 .read = seq_read,
186 .llseek = seq_lseek,
187 .release = single_release,
188};
cce585ce
MB
189
190static void rbtree_debugfs_init(struct regmap *map)
191{
192 debugfs_create_file("rbtree", 0400, map->debugfs, map, &rbtree_fops);
193}
194#else
195static void rbtree_debugfs_init(struct regmap *map)
196{
197}
bad2ab4b
MB
198#endif
199
28644c80
DP
200static int regcache_rbtree_init(struct regmap *map)
201{
202 struct regcache_rbtree_ctx *rbtree_ctx;
203 int i;
204 int ret;
205
206 map->cache = kmalloc(sizeof *rbtree_ctx, GFP_KERNEL);
207 if (!map->cache)
208 return -ENOMEM;
209
210 rbtree_ctx = map->cache;
211 rbtree_ctx->root = RB_ROOT;
212 rbtree_ctx->cached_rbnode = NULL;
213
214 for (i = 0; i < map->num_reg_defaults; i++) {
215 ret = regcache_rbtree_write(map,
216 map->reg_defaults[i].reg,
217 map->reg_defaults[i].def);
218 if (ret)
219 goto err;
220 }
221
cce585ce 222 rbtree_debugfs_init(map);
bad2ab4b 223
28644c80
DP
224 return 0;
225
226err:
462a185c 227 regcache_rbtree_exit(map);
28644c80
DP
228 return ret;
229}
230
231static int regcache_rbtree_exit(struct regmap *map)
232{
233 struct rb_node *next;
234 struct regcache_rbtree_ctx *rbtree_ctx;
235 struct regcache_rbtree_node *rbtree_node;
236
237 /* if we've already been called then just return */
238 rbtree_ctx = map->cache;
239 if (!rbtree_ctx)
240 return 0;
241
242 /* free up the rbtree */
243 next = rb_first(&rbtree_ctx->root);
244 while (next) {
245 rbtree_node = rb_entry(next, struct regcache_rbtree_node, node);
246 next = rb_next(&rbtree_node->node);
247 rb_erase(&rbtree_node->node, &rbtree_ctx->root);
248 kfree(rbtree_node->block);
249 kfree(rbtree_node);
250 }
251
252 /* release the resources */
253 kfree(map->cache);
254 map->cache = NULL;
255
256 return 0;
257}
258
259static int regcache_rbtree_read(struct regmap *map,
260 unsigned int reg, unsigned int *value)
261{
28644c80 262 struct regcache_rbtree_node *rbnode;
28644c80
DP
263 unsigned int reg_tmp;
264
3405addd 265 rbnode = regcache_rbtree_lookup(map, reg);
28644c80 266 if (rbnode) {
f01ee60f 267 reg_tmp = (reg - rbnode->base_reg) / map->reg_stride;
0c7ed856
DP
268 if (!regcache_reg_present(map, reg))
269 return -ENOENT;
879082c9 270 *value = regcache_rbtree_get_register(map, rbnode, reg_tmp);
28644c80 271 } else {
6e6ace00 272 return -ENOENT;
28644c80
DP
273 }
274
275 return 0;
276}
277
278
879082c9
MB
279static int regcache_rbtree_insert_to_block(struct regmap *map,
280 struct regcache_rbtree_node *rbnode,
28644c80 281 unsigned int pos, unsigned int reg,
879082c9 282 unsigned int value)
28644c80
DP
283{
284 u8 *blk;
285
286 blk = krealloc(rbnode->block,
879082c9
MB
287 (rbnode->blklen + 1) * map->cache_word_size,
288 GFP_KERNEL);
28644c80
DP
289 if (!blk)
290 return -ENOMEM;
291
292 /* insert the register value in the correct place in the rbnode block */
879082c9
MB
293 memmove(blk + (pos + 1) * map->cache_word_size,
294 blk + pos * map->cache_word_size,
295 (rbnode->blklen - pos) * map->cache_word_size);
28644c80
DP
296
297 /* update the rbnode block, its size and the base register */
298 rbnode->block = blk;
299 rbnode->blklen++;
300 if (!pos)
301 rbnode->base_reg = reg;
302
879082c9 303 regcache_rbtree_set_register(map, rbnode, pos, value);
28644c80
DP
304 return 0;
305}
306
0186645d
MB
307static struct regcache_rbtree_node *
308regcache_rbtree_node_alloc(struct regmap *map, unsigned int reg)
309{
310 struct regcache_rbtree_node *rbnode;
311
312 rbnode = kzalloc(sizeof(*rbnode), GFP_KERNEL);
313 if (!rbnode)
314 return NULL;
315
316 rbnode->blklen = sizeof(*rbnode);
317 rbnode->base_reg = reg;
318 rbnode->block = kmalloc(rbnode->blklen * map->cache_word_size,
319 GFP_KERNEL);
320 if (!rbnode->block) {
321 kfree(rbnode);
322 return NULL;
323 }
324
325 return rbnode;
326}
327
28644c80
DP
328static int regcache_rbtree_write(struct regmap *map, unsigned int reg,
329 unsigned int value)
330{
331 struct regcache_rbtree_ctx *rbtree_ctx;
332 struct regcache_rbtree_node *rbnode, *rbnode_tmp;
333 struct rb_node *node;
28644c80 334 unsigned int reg_tmp;
28644c80
DP
335 unsigned int pos;
336 int i;
337 int ret;
338
339 rbtree_ctx = map->cache;
0c7ed856 340 /* update the reg_present bitmap, make space if necessary */
78493f2d 341 ret = regcache_set_reg_present(map, reg);
0c7ed856
DP
342 if (ret < 0)
343 return ret;
0c7ed856 344
28644c80
DP
345 /* if we can't locate it in the cached rbnode we'll have
346 * to traverse the rbtree looking for it.
347 */
3405addd 348 rbnode = regcache_rbtree_lookup(map, reg);
28644c80 349 if (rbnode) {
f01ee60f 350 reg_tmp = (reg - rbnode->base_reg) / map->reg_stride;
879082c9 351 regcache_rbtree_set_register(map, rbnode, reg_tmp, value);
28644c80 352 } else {
28644c80
DP
353 /* look for an adjacent register to the one we are about to add */
354 for (node = rb_first(&rbtree_ctx->root); node;
355 node = rb_next(node)) {
f01ee60f
SW
356 rbnode_tmp = rb_entry(node, struct regcache_rbtree_node,
357 node);
28644c80 358 for (i = 0; i < rbnode_tmp->blklen; i++) {
f01ee60f
SW
359 reg_tmp = rbnode_tmp->base_reg +
360 (i * map->reg_stride);
361 if (abs(reg_tmp - reg) != map->reg_stride)
28644c80
DP
362 continue;
363 /* decide where in the block to place our register */
f01ee60f 364 if (reg_tmp + map->reg_stride == reg)
28644c80
DP
365 pos = i + 1;
366 else
367 pos = i;
879082c9
MB
368 ret = regcache_rbtree_insert_to_block(map,
369 rbnode_tmp,
370 pos, reg,
371 value);
28644c80
DP
372 if (ret)
373 return ret;
374 rbtree_ctx->cached_rbnode = rbnode_tmp;
375 return 0;
376 }
377 }
0186645d
MB
378
379 /* We did not manage to find a place to insert it in
380 * an existing block so create a new rbnode.
28644c80 381 */
0186645d 382 rbnode = regcache_rbtree_node_alloc(map, reg);
28644c80
DP
383 if (!rbnode)
384 return -ENOMEM;
0186645d
MB
385 regcache_rbtree_set_register(map, rbnode,
386 reg - rbnode->base_reg, value);
f01ee60f 387 regcache_rbtree_insert(map, &rbtree_ctx->root, rbnode);
28644c80
DP
388 rbtree_ctx->cached_rbnode = rbnode;
389 }
390
391 return 0;
392}
393
ac8d91c8
MB
394static int regcache_rbtree_sync(struct regmap *map, unsigned int min,
395 unsigned int max)
28644c80
DP
396{
397 struct regcache_rbtree_ctx *rbtree_ctx;
398 struct rb_node *node;
399 struct regcache_rbtree_node *rbnode;
28644c80 400 int ret;
f8bd822c 401 int base, end;
28644c80
DP
402
403 rbtree_ctx = map->cache;
404 for (node = rb_first(&rbtree_ctx->root); node; node = rb_next(node)) {
405 rbnode = rb_entry(node, struct regcache_rbtree_node, node);
ac8d91c8
MB
406
407 if (rbnode->base_reg < min)
408 continue;
409 if (rbnode->base_reg > max)
410 break;
411 if (rbnode->base_reg + rbnode->blklen < min)
412 continue;
413
f9353e70 414 if (min > rbnode->base_reg)
ac8d91c8
MB
415 base = min - rbnode->base_reg;
416 else
417 base = 0;
418
419 if (max < rbnode->base_reg + rbnode->blklen)
8abac3ba 420 end = max - rbnode->base_reg + 1;
ac8d91c8
MB
421 else
422 end = rbnode->blklen;
423
f8bd822c
MB
424 ret = regcache_sync_block(map, rbnode->block, rbnode->base_reg,
425 base, end);
426 if (ret != 0)
427 return ret;
28644c80
DP
428 }
429
f8bd822c 430 return regmap_async_complete(map);
28644c80
DP
431}
432
433struct regcache_ops regcache_rbtree_ops = {
434 .type = REGCACHE_RBTREE,
435 .name = "rbtree",
436 .init = regcache_rbtree_init,
437 .exit = regcache_rbtree_exit,
438 .read = regcache_rbtree_read,
439 .write = regcache_rbtree_write,
440 .sync = regcache_rbtree_sync
441};
This page took 0.14189 seconds and 5 git commands to generate.