2 * Register cache access API - rbtree caching support
4 * Copyright 2011 Wolfson Microelectronics plc
6 * Author: Dimitris Papastamos <dp@opensource.wolfsonmicro.com>
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.
13 #include <linux/slab.h>
14 #include <linux/device.h>
15 #include <linux/debugfs.h>
16 #include <linux/rbtree.h>
17 #include <linux/seq_file.h>
21 static int regcache_rbtree_write(struct regmap
*map
, unsigned int reg
,
23 static int regcache_rbtree_exit(struct regmap
*map
);
25 struct regcache_rbtree_node
{
26 /* the actual rbtree node holding this block */
28 /* base register handled by this block */
29 unsigned int base_reg
;
30 /* block of adjacent registers */
32 /* number of registers available in the block */
34 } __attribute__ ((packed
));
36 struct regcache_rbtree_ctx
{
38 struct regcache_rbtree_node
*cached_rbnode
;
41 static inline void regcache_rbtree_get_base_top_reg(
43 struct regcache_rbtree_node
*rbnode
,
44 unsigned int *base
, unsigned int *top
)
46 *base
= rbnode
->base_reg
;
47 *top
= rbnode
->base_reg
+ ((rbnode
->blklen
- 1) * map
->reg_stride
);
50 static unsigned int regcache_rbtree_get_register(struct regmap
*map
,
51 struct regcache_rbtree_node
*rbnode
, unsigned int idx
)
53 return regcache_get_val(map
, rbnode
->block
, idx
);
56 static void regcache_rbtree_set_register(struct regmap
*map
,
57 struct regcache_rbtree_node
*rbnode
,
58 unsigned int idx
, unsigned int val
)
60 regcache_set_val(map
, rbnode
->block
, idx
, val
);
63 static struct regcache_rbtree_node
*regcache_rbtree_lookup(struct regmap
*map
,
66 struct regcache_rbtree_ctx
*rbtree_ctx
= map
->cache
;
68 struct regcache_rbtree_node
*rbnode
;
69 unsigned int base_reg
, top_reg
;
71 rbnode
= rbtree_ctx
->cached_rbnode
;
73 regcache_rbtree_get_base_top_reg(map
, rbnode
, &base_reg
,
75 if (reg
>= base_reg
&& reg
<= top_reg
)
79 node
= rbtree_ctx
->root
.rb_node
;
81 rbnode
= container_of(node
, struct regcache_rbtree_node
, node
);
82 regcache_rbtree_get_base_top_reg(map
, rbnode
, &base_reg
,
84 if (reg
>= base_reg
&& reg
<= top_reg
) {
85 rbtree_ctx
->cached_rbnode
= rbnode
;
87 } else if (reg
> top_reg
) {
88 node
= node
->rb_right
;
89 } else if (reg
< base_reg
) {
97 static int regcache_rbtree_insert(struct regmap
*map
, struct rb_root
*root
,
98 struct regcache_rbtree_node
*rbnode
)
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
;
106 new = &root
->rb_node
;
108 rbnode_tmp
= container_of(*new, struct regcache_rbtree_node
,
110 /* base and top registers of the current rbnode */
111 regcache_rbtree_get_base_top_reg(map
, rbnode_tmp
, &base_reg_tmp
,
113 /* base register of the rbnode to be added */
114 base_reg
= rbnode
->base_reg
;
116 /* if this register has already been inserted, just return */
117 if (base_reg
>= base_reg_tmp
&&
118 base_reg
<= top_reg_tmp
)
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
);
126 /* insert the node into the rbtree */
127 rb_link_node(&rbnode
->node
, parent
, new);
128 rb_insert_color(&rbnode
->node
, root
);
133 #ifdef CONFIG_DEBUG_FS
134 static int rbtree_show(struct seq_file
*s
, void *ignored
)
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
;
144 int this_registers
, average
;
148 mem_size
= sizeof(*rbtree_ctx
);
149 mem_size
+= BITS_TO_LONGS(map
->cache_present_nbits
) * sizeof(long);
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
);
154 mem_size
+= sizeof(*n
);
155 mem_size
+= (n
->blklen
* map
->cache_word_size
);
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
);
162 registers
+= this_registers
;
166 average
= registers
/ nodes
;
170 seq_printf(s
, "%d nodes, %d registers, average %d registers, used %zu bytes\n",
171 nodes
, registers
, average
, mem_size
);
178 static int rbtree_open(struct inode
*inode
, struct file
*file
)
180 return single_open(file
, rbtree_show
, inode
->i_private
);
183 static const struct file_operations rbtree_fops
= {
187 .release
= single_release
,
190 static void rbtree_debugfs_init(struct regmap
*map
)
192 debugfs_create_file("rbtree", 0400, map
->debugfs
, map
, &rbtree_fops
);
195 static void rbtree_debugfs_init(struct regmap
*map
)
200 static int regcache_rbtree_init(struct regmap
*map
)
202 struct regcache_rbtree_ctx
*rbtree_ctx
;
206 map
->cache
= kmalloc(sizeof *rbtree_ctx
, GFP_KERNEL
);
210 rbtree_ctx
= map
->cache
;
211 rbtree_ctx
->root
= RB_ROOT
;
212 rbtree_ctx
->cached_rbnode
= NULL
;
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
);
222 rbtree_debugfs_init(map
);
227 regcache_rbtree_exit(map
);
231 static int regcache_rbtree_exit(struct regmap
*map
)
233 struct rb_node
*next
;
234 struct regcache_rbtree_ctx
*rbtree_ctx
;
235 struct regcache_rbtree_node
*rbtree_node
;
237 /* if we've already been called then just return */
238 rbtree_ctx
= map
->cache
;
242 /* free up the rbtree */
243 next
= rb_first(&rbtree_ctx
->root
);
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
);
252 /* release the resources */
259 static int regcache_rbtree_read(struct regmap
*map
,
260 unsigned int reg
, unsigned int *value
)
262 struct regcache_rbtree_node
*rbnode
;
263 unsigned int reg_tmp
;
265 rbnode
= regcache_rbtree_lookup(map
, reg
);
267 reg_tmp
= (reg
- rbnode
->base_reg
) / map
->reg_stride
;
268 if (!regcache_reg_present(map
, reg
))
270 *value
= regcache_rbtree_get_register(map
, rbnode
, reg_tmp
);
279 static int regcache_rbtree_insert_to_block(struct regmap
*map
,
280 struct regcache_rbtree_node
*rbnode
,
281 unsigned int pos
, unsigned int reg
,
286 blk
= krealloc(rbnode
->block
,
287 (rbnode
->blklen
+ 1) * map
->cache_word_size
,
292 /* insert the register value in the correct place in the rbnode block */
293 memmove(blk
+ (pos
+ 1) * map
->cache_word_size
,
294 blk
+ pos
* map
->cache_word_size
,
295 (rbnode
->blklen
- pos
) * map
->cache_word_size
);
297 /* update the rbnode block, its size and the base register */
301 rbnode
->base_reg
= reg
;
303 regcache_rbtree_set_register(map
, rbnode
, pos
, value
);
307 static int regcache_rbtree_write(struct regmap
*map
, unsigned int reg
,
310 struct regcache_rbtree_ctx
*rbtree_ctx
;
311 struct regcache_rbtree_node
*rbnode
, *rbnode_tmp
;
312 struct rb_node
*node
;
313 unsigned int reg_tmp
;
318 rbtree_ctx
= map
->cache
;
319 /* update the reg_present bitmap, make space if necessary */
320 ret
= regcache_set_reg_present(map
, reg
);
324 /* if we can't locate it in the cached rbnode we'll have
325 * to traverse the rbtree looking for it.
327 rbnode
= regcache_rbtree_lookup(map
, reg
);
329 reg_tmp
= (reg
- rbnode
->base_reg
) / map
->reg_stride
;
330 regcache_rbtree_set_register(map
, rbnode
, reg_tmp
, value
);
332 /* look for an adjacent register to the one we are about to add */
333 for (node
= rb_first(&rbtree_ctx
->root
); node
;
334 node
= rb_next(node
)) {
335 rbnode_tmp
= rb_entry(node
, struct regcache_rbtree_node
,
337 for (i
= 0; i
< rbnode_tmp
->blklen
; i
++) {
338 reg_tmp
= rbnode_tmp
->base_reg
+
339 (i
* map
->reg_stride
);
340 if (abs(reg_tmp
- reg
) != map
->reg_stride
)
342 /* decide where in the block to place our register */
343 if (reg_tmp
+ map
->reg_stride
== reg
)
347 ret
= regcache_rbtree_insert_to_block(map
,
353 rbtree_ctx
->cached_rbnode
= rbnode_tmp
;
357 /* we did not manage to find a place to insert it in an existing
358 * block so create a new rbnode with a single register in its block.
359 * This block will get populated further if any other adjacent
360 * registers get modified in the future.
362 rbnode
= kzalloc(sizeof *rbnode
, GFP_KERNEL
);
365 rbnode
->blklen
= sizeof(*rbnode
);
366 rbnode
->base_reg
= reg
;
367 rbnode
->block
= kmalloc(rbnode
->blklen
* map
->cache_word_size
,
369 if (!rbnode
->block
) {
373 regcache_rbtree_set_register(map
, rbnode
, 0, value
);
374 regcache_rbtree_insert(map
, &rbtree_ctx
->root
, rbnode
);
375 rbtree_ctx
->cached_rbnode
= rbnode
;
381 static int regcache_rbtree_sync(struct regmap
*map
, unsigned int min
,
384 struct regcache_rbtree_ctx
*rbtree_ctx
;
385 struct rb_node
*node
;
386 struct regcache_rbtree_node
*rbnode
;
390 rbtree_ctx
= map
->cache
;
391 for (node
= rb_first(&rbtree_ctx
->root
); node
; node
= rb_next(node
)) {
392 rbnode
= rb_entry(node
, struct regcache_rbtree_node
, node
);
394 if (rbnode
->base_reg
< min
)
396 if (rbnode
->base_reg
> max
)
398 if (rbnode
->base_reg
+ rbnode
->blklen
< min
)
401 if (min
> rbnode
->base_reg
)
402 base
= min
- rbnode
->base_reg
;
406 if (max
< rbnode
->base_reg
+ rbnode
->blklen
)
407 end
= max
- rbnode
->base_reg
+ 1;
409 end
= rbnode
->blklen
;
411 ret
= regcache_sync_block(map
, rbnode
->block
, rbnode
->base_reg
,
417 return regmap_async_complete(map
);
420 struct regcache_ops regcache_rbtree_ops
= {
421 .type
= REGCACHE_RBTREE
,
423 .init
= regcache_rbtree_init
,
424 .exit
= regcache_rbtree_exit
,
425 .read
= regcache_rbtree_read
,
426 .write
= regcache_rbtree_write
,
427 .sync
= regcache_rbtree_sync