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(
42 struct regcache_rbtree_node
*rbnode
,
43 unsigned int *base
, unsigned int *top
)
45 *base
= rbnode
->base_reg
;
46 *top
= rbnode
->base_reg
+ rbnode
->blklen
- 1;
49 static unsigned int regcache_rbtree_get_register(
50 struct regcache_rbtree_node
*rbnode
, unsigned int idx
,
51 unsigned int word_size
)
53 return regcache_get_val(rbnode
->block
, idx
, word_size
);
56 static void regcache_rbtree_set_register(struct regcache_rbtree_node
*rbnode
,
57 unsigned int idx
, unsigned int val
,
58 unsigned int word_size
)
60 regcache_set_val(rbnode
->block
, idx
, val
, word_size
);
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(rbnode
, &base_reg
, &top_reg
);
74 if (reg
>= base_reg
&& reg
<= top_reg
)
78 node
= rbtree_ctx
->root
.rb_node
;
80 rbnode
= container_of(node
, struct regcache_rbtree_node
, node
);
81 regcache_rbtree_get_base_top_reg(rbnode
, &base_reg
, &top_reg
);
82 if (reg
>= base_reg
&& reg
<= top_reg
) {
83 rbtree_ctx
->cached_rbnode
= rbnode
;
85 } else if (reg
> top_reg
) {
86 node
= node
->rb_right
;
87 } else if (reg
< base_reg
) {
95 static int regcache_rbtree_insert(struct rb_root
*root
,
96 struct regcache_rbtree_node
*rbnode
)
98 struct rb_node
**new, *parent
;
99 struct regcache_rbtree_node
*rbnode_tmp
;
100 unsigned int base_reg_tmp
, top_reg_tmp
;
101 unsigned int base_reg
;
104 new = &root
->rb_node
;
106 rbnode_tmp
= container_of(*new, struct regcache_rbtree_node
,
108 /* base and top registers of the current rbnode */
109 regcache_rbtree_get_base_top_reg(rbnode_tmp
, &base_reg_tmp
,
111 /* base register of the rbnode to be added */
112 base_reg
= rbnode
->base_reg
;
114 /* if this register has already been inserted, just return */
115 if (base_reg
>= base_reg_tmp
&&
116 base_reg
<= top_reg_tmp
)
118 else if (base_reg
> top_reg_tmp
)
119 new = &((*new)->rb_right
);
120 else if (base_reg
< base_reg_tmp
)
121 new = &((*new)->rb_left
);
124 /* insert the node into the rbtree */
125 rb_link_node(&rbnode
->node
, parent
, new);
126 rb_insert_color(&rbnode
->node
, root
);
131 #ifdef CONFIG_DEBUG_FS
132 static int rbtree_show(struct seq_file
*s
, void *ignored
)
134 struct regmap
*map
= s
->private;
135 struct regcache_rbtree_ctx
*rbtree_ctx
= map
->cache
;
136 struct regcache_rbtree_node
*n
;
137 struct rb_node
*node
;
138 unsigned int base
, top
;
142 mutex_lock(&map
->lock
);
144 for (node
= rb_first(&rbtree_ctx
->root
); node
!= NULL
;
145 node
= rb_next(node
)) {
146 n
= container_of(node
, struct regcache_rbtree_node
, node
);
148 regcache_rbtree_get_base_top_reg(n
, &base
, &top
);
149 seq_printf(s
, "%x-%x (%d)\n", base
, top
, top
- base
+ 1);
152 registers
+= top
- base
+ 1;
155 seq_printf(s
, "%d nodes, %d registers, average %d registers\n",
156 nodes
, registers
, registers
/ nodes
);
158 mutex_unlock(&map
->lock
);
163 static int rbtree_open(struct inode
*inode
, struct file
*file
)
165 return single_open(file
, rbtree_show
, inode
->i_private
);
168 static const struct file_operations rbtree_fops
= {
172 .release
= single_release
,
175 static void rbtree_debugfs_init(struct regmap
*map
)
177 debugfs_create_file("rbtree", 0400, map
->debugfs
, map
, &rbtree_fops
);
180 static void rbtree_debugfs_init(struct regmap
*map
)
185 static int regcache_rbtree_init(struct regmap
*map
)
187 struct regcache_rbtree_ctx
*rbtree_ctx
;
191 map
->cache
= kmalloc(sizeof *rbtree_ctx
, GFP_KERNEL
);
195 rbtree_ctx
= map
->cache
;
196 rbtree_ctx
->root
= RB_ROOT
;
197 rbtree_ctx
->cached_rbnode
= NULL
;
199 for (i
= 0; i
< map
->num_reg_defaults
; i
++) {
200 ret
= regcache_rbtree_write(map
,
201 map
->reg_defaults
[i
].reg
,
202 map
->reg_defaults
[i
].def
);
207 rbtree_debugfs_init(map
);
212 regcache_rbtree_exit(map
);
216 static int regcache_rbtree_exit(struct regmap
*map
)
218 struct rb_node
*next
;
219 struct regcache_rbtree_ctx
*rbtree_ctx
;
220 struct regcache_rbtree_node
*rbtree_node
;
222 /* if we've already been called then just return */
223 rbtree_ctx
= map
->cache
;
227 /* free up the rbtree */
228 next
= rb_first(&rbtree_ctx
->root
);
230 rbtree_node
= rb_entry(next
, struct regcache_rbtree_node
, node
);
231 next
= rb_next(&rbtree_node
->node
);
232 rb_erase(&rbtree_node
->node
, &rbtree_ctx
->root
);
233 kfree(rbtree_node
->block
);
237 /* release the resources */
244 static int regcache_rbtree_read(struct regmap
*map
,
245 unsigned int reg
, unsigned int *value
)
247 struct regcache_rbtree_node
*rbnode
;
248 unsigned int reg_tmp
;
250 rbnode
= regcache_rbtree_lookup(map
, reg
);
252 reg_tmp
= reg
- rbnode
->base_reg
;
253 *value
= regcache_rbtree_get_register(rbnode
, reg_tmp
,
254 map
->cache_word_size
);
263 static int regcache_rbtree_insert_to_block(struct regcache_rbtree_node
*rbnode
,
264 unsigned int pos
, unsigned int reg
,
265 unsigned int value
, unsigned int word_size
)
269 blk
= krealloc(rbnode
->block
,
270 (rbnode
->blklen
+ 1) * word_size
, GFP_KERNEL
);
274 /* insert the register value in the correct place in the rbnode block */
275 memmove(blk
+ (pos
+ 1) * word_size
,
276 blk
+ pos
* word_size
,
277 (rbnode
->blklen
- pos
) * word_size
);
279 /* update the rbnode block, its size and the base register */
283 rbnode
->base_reg
= reg
;
285 regcache_rbtree_set_register(rbnode
, pos
, value
, word_size
);
289 static int regcache_rbtree_write(struct regmap
*map
, unsigned int reg
,
292 struct regcache_rbtree_ctx
*rbtree_ctx
;
293 struct regcache_rbtree_node
*rbnode
, *rbnode_tmp
;
294 struct rb_node
*node
;
296 unsigned int reg_tmp
;
301 rbtree_ctx
= map
->cache
;
302 /* if we can't locate it in the cached rbnode we'll have
303 * to traverse the rbtree looking for it.
305 rbnode
= regcache_rbtree_lookup(map
, reg
);
307 reg_tmp
= reg
- rbnode
->base_reg
;
308 val
= regcache_rbtree_get_register(rbnode
, reg_tmp
,
309 map
->cache_word_size
);
312 regcache_rbtree_set_register(rbnode
, reg_tmp
, value
,
313 map
->cache_word_size
);
315 /* look for an adjacent register to the one we are about to add */
316 for (node
= rb_first(&rbtree_ctx
->root
); node
;
317 node
= rb_next(node
)) {
318 rbnode_tmp
= rb_entry(node
, struct regcache_rbtree_node
, node
);
319 for (i
= 0; i
< rbnode_tmp
->blklen
; i
++) {
320 reg_tmp
= rbnode_tmp
->base_reg
+ i
;
321 if (abs(reg_tmp
- reg
) != 1)
323 /* decide where in the block to place our register */
324 if (reg_tmp
+ 1 == reg
)
328 ret
= regcache_rbtree_insert_to_block(rbnode_tmp
, pos
,
330 map
->cache_word_size
);
333 rbtree_ctx
->cached_rbnode
= rbnode_tmp
;
337 /* we did not manage to find a place to insert it in an existing
338 * block so create a new rbnode with a single register in its block.
339 * This block will get populated further if any other adjacent
340 * registers get modified in the future.
342 rbnode
= kzalloc(sizeof *rbnode
, GFP_KERNEL
);
346 rbnode
->base_reg
= reg
;
347 rbnode
->block
= kmalloc(rbnode
->blklen
* map
->cache_word_size
,
349 if (!rbnode
->block
) {
353 regcache_rbtree_set_register(rbnode
, 0, value
, map
->cache_word_size
);
354 regcache_rbtree_insert(&rbtree_ctx
->root
, rbnode
);
355 rbtree_ctx
->cached_rbnode
= rbnode
;
361 static int regcache_rbtree_sync(struct regmap
*map
)
363 struct regcache_rbtree_ctx
*rbtree_ctx
;
364 struct rb_node
*node
;
365 struct regcache_rbtree_node
*rbnode
;
371 rbtree_ctx
= map
->cache
;
372 for (node
= rb_first(&rbtree_ctx
->root
); node
; node
= rb_next(node
)) {
373 rbnode
= rb_entry(node
, struct regcache_rbtree_node
, node
);
374 for (i
= 0; i
< rbnode
->blklen
; i
++) {
375 regtmp
= rbnode
->base_reg
+ i
;
376 val
= regcache_rbtree_get_register(rbnode
, i
,
377 map
->cache_word_size
);
379 /* Is this the hardware default? If so skip. */
380 ret
= regcache_lookup_reg(map
, i
);
381 if (ret
> 0 && val
== map
->reg_defaults
[ret
].def
)
384 map
->cache_bypass
= 1;
385 ret
= _regmap_write(map
, regtmp
, val
);
386 map
->cache_bypass
= 0;
389 dev_dbg(map
->dev
, "Synced register %#x, value %#x\n",
397 struct regcache_ops regcache_rbtree_ops
= {
398 .type
= REGCACHE_RBTREE
,
400 .init
= regcache_rbtree_init
,
401 .exit
= regcache_rbtree_exit
,
402 .read
= regcache_rbtree_read
,
403 .write
= regcache_rbtree_write
,
404 .sync
= regcache_rbtree_sync