Commit | Line | Data |
---|---|---|
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 | ||
21 | static int regcache_rbtree_write(struct regmap *map, unsigned int reg, | |
22 | unsigned int value); | |
462a185c | 23 | static int regcache_rbtree_exit(struct regmap *map); |
28644c80 DP |
24 | |
25 | struct 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 | ||
36 | struct regcache_rbtree_ctx { | |
37 | struct rb_root root; | |
38 | struct regcache_rbtree_node *cached_rbnode; | |
39 | }; | |
40 | ||
41 | static 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 |
50 | static 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 |
56 | static 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 | 63 | static 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 | 97 | static 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 |
134 | static 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 | ||
178 | static int rbtree_open(struct inode *inode, struct file *file) | |
179 | { | |
180 | return single_open(file, rbtree_show, inode->i_private); | |
181 | } | |
182 | ||
183 | static 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 | |
190 | static void rbtree_debugfs_init(struct regmap *map) | |
191 | { | |
192 | debugfs_create_file("rbtree", 0400, map->debugfs, map, &rbtree_fops); | |
193 | } | |
194 | #else | |
195 | static void rbtree_debugfs_init(struct regmap *map) | |
196 | { | |
197 | } | |
bad2ab4b MB |
198 | #endif |
199 | ||
28644c80 DP |
200 | static 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 | ||
226 | err: | |
462a185c | 227 | regcache_rbtree_exit(map); |
28644c80 DP |
228 | return ret; |
229 | } | |
230 | ||
231 | static 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 | ||
259 | static 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 |
279 | static 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 | ||
307 | static int regcache_rbtree_write(struct regmap *map, unsigned int reg, | |
308 | unsigned int value) | |
309 | { | |
310 | struct regcache_rbtree_ctx *rbtree_ctx; | |
311 | struct regcache_rbtree_node *rbnode, *rbnode_tmp; | |
312 | struct rb_node *node; | |
28644c80 | 313 | unsigned int reg_tmp; |
28644c80 DP |
314 | unsigned int pos; |
315 | int i; | |
316 | int ret; | |
317 | ||
318 | rbtree_ctx = map->cache; | |
0c7ed856 | 319 | /* update the reg_present bitmap, make space if necessary */ |
78493f2d | 320 | ret = regcache_set_reg_present(map, reg); |
0c7ed856 DP |
321 | if (ret < 0) |
322 | return ret; | |
0c7ed856 | 323 | |
28644c80 DP |
324 | /* if we can't locate it in the cached rbnode we'll have |
325 | * to traverse the rbtree looking for it. | |
326 | */ | |
3405addd | 327 | rbnode = regcache_rbtree_lookup(map, reg); |
28644c80 | 328 | if (rbnode) { |
f01ee60f | 329 | reg_tmp = (reg - rbnode->base_reg) / map->reg_stride; |
879082c9 | 330 | regcache_rbtree_set_register(map, rbnode, reg_tmp, value); |
28644c80 | 331 | } else { |
28644c80 DP |
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)) { | |
f01ee60f SW |
335 | rbnode_tmp = rb_entry(node, struct regcache_rbtree_node, |
336 | node); | |
28644c80 | 337 | for (i = 0; i < rbnode_tmp->blklen; i++) { |
f01ee60f SW |
338 | reg_tmp = rbnode_tmp->base_reg + |
339 | (i * map->reg_stride); | |
340 | if (abs(reg_tmp - reg) != map->reg_stride) | |
28644c80 DP |
341 | continue; |
342 | /* decide where in the block to place our register */ | |
f01ee60f | 343 | if (reg_tmp + map->reg_stride == reg) |
28644c80 DP |
344 | pos = i + 1; |
345 | else | |
346 | pos = i; | |
879082c9 MB |
347 | ret = regcache_rbtree_insert_to_block(map, |
348 | rbnode_tmp, | |
349 | pos, reg, | |
350 | value); | |
28644c80 DP |
351 | if (ret) |
352 | return ret; | |
353 | rbtree_ctx->cached_rbnode = rbnode_tmp; | |
354 | return 0; | |
355 | } | |
356 | } | |
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. | |
361 | */ | |
362 | rbnode = kzalloc(sizeof *rbnode, GFP_KERNEL); | |
363 | if (!rbnode) | |
364 | return -ENOMEM; | |
0c7ed856 | 365 | rbnode->blklen = sizeof(*rbnode); |
28644c80 | 366 | rbnode->base_reg = reg; |
25ed1156 | 367 | rbnode->block = kmalloc(rbnode->blklen * map->cache_word_size, |
28644c80 DP |
368 | GFP_KERNEL); |
369 | if (!rbnode->block) { | |
370 | kfree(rbnode); | |
371 | return -ENOMEM; | |
372 | } | |
879082c9 | 373 | regcache_rbtree_set_register(map, rbnode, 0, value); |
f01ee60f | 374 | regcache_rbtree_insert(map, &rbtree_ctx->root, rbnode); |
28644c80 DP |
375 | rbtree_ctx->cached_rbnode = rbnode; |
376 | } | |
377 | ||
378 | return 0; | |
379 | } | |
380 | ||
ac8d91c8 MB |
381 | static int regcache_rbtree_sync(struct regmap *map, unsigned int min, |
382 | unsigned int max) | |
28644c80 DP |
383 | { |
384 | struct regcache_rbtree_ctx *rbtree_ctx; | |
385 | struct rb_node *node; | |
386 | struct regcache_rbtree_node *rbnode; | |
28644c80 | 387 | int ret; |
f8bd822c | 388 | int base, end; |
28644c80 DP |
389 | |
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); | |
ac8d91c8 MB |
393 | |
394 | if (rbnode->base_reg < min) | |
395 | continue; | |
396 | if (rbnode->base_reg > max) | |
397 | break; | |
398 | if (rbnode->base_reg + rbnode->blklen < min) | |
399 | continue; | |
400 | ||
f9353e70 | 401 | if (min > rbnode->base_reg) |
ac8d91c8 MB |
402 | base = min - rbnode->base_reg; |
403 | else | |
404 | base = 0; | |
405 | ||
406 | if (max < rbnode->base_reg + rbnode->blklen) | |
8abac3ba | 407 | end = max - rbnode->base_reg + 1; |
ac8d91c8 MB |
408 | else |
409 | end = rbnode->blklen; | |
410 | ||
f8bd822c MB |
411 | ret = regcache_sync_block(map, rbnode->block, rbnode->base_reg, |
412 | base, end); | |
413 | if (ret != 0) | |
414 | return ret; | |
28644c80 DP |
415 | } |
416 | ||
f8bd822c | 417 | return regmap_async_complete(map); |
28644c80 DP |
418 | } |
419 | ||
420 | struct regcache_ops regcache_rbtree_ops = { | |
421 | .type = REGCACHE_RBTREE, | |
422 | .name = "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 | |
428 | }; |