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
;
143 int this_registers
, average
;
147 for (node
= rb_first(&rbtree_ctx
->root
); node
!= NULL
;
148 node
= rb_next(node
)) {
149 n
= container_of(node
, struct regcache_rbtree_node
, node
);
151 regcache_rbtree_get_base_top_reg(map
, n
, &base
, &top
);
152 this_registers
= ((top
- base
) / map
->reg_stride
) + 1;
153 seq_printf(s
, "%x-%x (%d)\n", base
, top
, this_registers
);
156 registers
+= this_registers
;
160 average
= registers
/ nodes
;
164 seq_printf(s
, "%d nodes, %d registers, average %d registers\n",
165 nodes
, registers
, average
);
172 static int rbtree_open(struct inode
*inode
, struct file
*file
)
174 return single_open(file
, rbtree_show
, inode
->i_private
);
177 static const struct file_operations rbtree_fops
= {
181 .release
= single_release
,
184 static void rbtree_debugfs_init(struct regmap
*map
)
186 debugfs_create_file("rbtree", 0400, map
->debugfs
, map
, &rbtree_fops
);
189 static void rbtree_debugfs_init(struct regmap
*map
)
194 static int regcache_rbtree_init(struct regmap
*map
)
196 struct regcache_rbtree_ctx
*rbtree_ctx
;
200 map
->cache
= kmalloc(sizeof *rbtree_ctx
, GFP_KERNEL
);
204 rbtree_ctx
= map
->cache
;
205 rbtree_ctx
->root
= RB_ROOT
;
206 rbtree_ctx
->cached_rbnode
= NULL
;
208 for (i
= 0; i
< map
->num_reg_defaults
; i
++) {
209 ret
= regcache_rbtree_write(map
,
210 map
->reg_defaults
[i
].reg
,
211 map
->reg_defaults
[i
].def
);
216 rbtree_debugfs_init(map
);
221 regcache_rbtree_exit(map
);
225 static int regcache_rbtree_exit(struct regmap
*map
)
227 struct rb_node
*next
;
228 struct regcache_rbtree_ctx
*rbtree_ctx
;
229 struct regcache_rbtree_node
*rbtree_node
;
231 /* if we've already been called then just return */
232 rbtree_ctx
= map
->cache
;
236 /* free up the rbtree */
237 next
= rb_first(&rbtree_ctx
->root
);
239 rbtree_node
= rb_entry(next
, struct regcache_rbtree_node
, node
);
240 next
= rb_next(&rbtree_node
->node
);
241 rb_erase(&rbtree_node
->node
, &rbtree_ctx
->root
);
242 kfree(rbtree_node
->block
);
246 /* release the resources */
253 static int regcache_rbtree_read(struct regmap
*map
,
254 unsigned int reg
, unsigned int *value
)
256 struct regcache_rbtree_node
*rbnode
;
257 unsigned int reg_tmp
;
259 rbnode
= regcache_rbtree_lookup(map
, reg
);
261 reg_tmp
= (reg
- rbnode
->base_reg
) / map
->reg_stride
;
262 *value
= regcache_rbtree_get_register(map
, rbnode
, reg_tmp
);
271 static int regcache_rbtree_insert_to_block(struct regmap
*map
,
272 struct regcache_rbtree_node
*rbnode
,
273 unsigned int pos
, unsigned int reg
,
278 blk
= krealloc(rbnode
->block
,
279 (rbnode
->blklen
+ 1) * map
->cache_word_size
,
284 /* insert the register value in the correct place in the rbnode block */
285 memmove(blk
+ (pos
+ 1) * map
->cache_word_size
,
286 blk
+ pos
* map
->cache_word_size
,
287 (rbnode
->blklen
- pos
) * map
->cache_word_size
);
289 /* update the rbnode block, its size and the base register */
293 rbnode
->base_reg
= reg
;
295 regcache_rbtree_set_register(map
, rbnode
, pos
, value
);
299 static int regcache_rbtree_write(struct regmap
*map
, unsigned int reg
,
302 struct regcache_rbtree_ctx
*rbtree_ctx
;
303 struct regcache_rbtree_node
*rbnode
, *rbnode_tmp
;
304 struct rb_node
*node
;
305 unsigned int reg_tmp
;
310 rbtree_ctx
= map
->cache
;
311 /* if we can't locate it in the cached rbnode we'll have
312 * to traverse the rbtree looking for it.
314 rbnode
= regcache_rbtree_lookup(map
, reg
);
316 reg_tmp
= (reg
- rbnode
->base_reg
) / map
->reg_stride
;
317 regcache_rbtree_set_register(map
, rbnode
, reg_tmp
, value
);
319 /* look for an adjacent register to the one we are about to add */
320 for (node
= rb_first(&rbtree_ctx
->root
); node
;
321 node
= rb_next(node
)) {
322 rbnode_tmp
= rb_entry(node
, struct regcache_rbtree_node
,
324 for (i
= 0; i
< rbnode_tmp
->blklen
; i
++) {
325 reg_tmp
= rbnode_tmp
->base_reg
+
326 (i
* map
->reg_stride
);
327 if (abs(reg_tmp
- reg
) != map
->reg_stride
)
329 /* decide where in the block to place our register */
330 if (reg_tmp
+ map
->reg_stride
== reg
)
334 ret
= regcache_rbtree_insert_to_block(map
,
340 rbtree_ctx
->cached_rbnode
= rbnode_tmp
;
344 /* we did not manage to find a place to insert it in an existing
345 * block so create a new rbnode with a single register in its block.
346 * This block will get populated further if any other adjacent
347 * registers get modified in the future.
349 rbnode
= kzalloc(sizeof *rbnode
, GFP_KERNEL
);
353 rbnode
->base_reg
= reg
;
354 rbnode
->block
= kmalloc(rbnode
->blklen
* map
->cache_word_size
,
356 if (!rbnode
->block
) {
360 regcache_rbtree_set_register(map
, rbnode
, 0, value
);
361 regcache_rbtree_insert(map
, &rbtree_ctx
->root
, rbnode
);
362 rbtree_ctx
->cached_rbnode
= rbnode
;
368 static int regcache_rbtree_sync(struct regmap
*map
, unsigned int min
,
371 struct regcache_rbtree_ctx
*rbtree_ctx
;
372 struct rb_node
*node
;
373 struct regcache_rbtree_node
*rbnode
;
379 rbtree_ctx
= map
->cache
;
380 for (node
= rb_first(&rbtree_ctx
->root
); node
; node
= rb_next(node
)) {
381 rbnode
= rb_entry(node
, struct regcache_rbtree_node
, node
);
383 if (rbnode
->base_reg
< min
)
385 if (rbnode
->base_reg
> max
)
387 if (rbnode
->base_reg
+ rbnode
->blklen
< min
)
390 if (min
> rbnode
->base_reg
)
391 base
= min
- rbnode
->base_reg
;
395 if (max
< rbnode
->base_reg
+ rbnode
->blklen
)
396 end
= rbnode
->base_reg
+ rbnode
->blklen
- max
;
398 end
= rbnode
->blklen
;
400 for (i
= base
; i
< end
; i
++) {
401 regtmp
= rbnode
->base_reg
+ (i
* map
->reg_stride
);
402 val
= regcache_rbtree_get_register(map
, rbnode
, i
);
404 /* Is this the hardware default? If so skip. */
405 ret
= regcache_lookup_reg(map
, regtmp
);
406 if (ret
>= 0 && val
== map
->reg_defaults
[ret
].def
)
409 map
->cache_bypass
= 1;
410 ret
= _regmap_write(map
, regtmp
, val
);
411 map
->cache_bypass
= 0;
414 dev_dbg(map
->dev
, "Synced register %#x, value %#x\n",
422 struct regcache_ops regcache_rbtree_ops
= {
423 .type
= REGCACHE_RBTREE
,
425 .init
= regcache_rbtree_init
,
426 .exit
= regcache_rbtree_exit
,
427 .read
= regcache_rbtree_read
,
428 .write
= regcache_rbtree_write
,
429 .sync
= regcache_rbtree_sync