drivers/base/regmap/regcache-rbtree.c

   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>
  14 #include <linux/device.h>
  15 #include <linux/debugfs.h>
  16 #include <linux/rbtree.h>
  17 #include <linux/seq_file.h>
  18
  19 #include "internal.h"
  20
  21 static int regcache_rbtree_write(struct regmap *map, unsigned int reg,
  22                                  unsigned int value);
  23 static int regcache_rbtree_exit(struct regmap *map);
  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;
  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(
  42         struct regcache_rbtree_node *rbnode,
  43         unsigned int *base, unsigned int *top)
  44 {
  45         *base = rbnode->base_reg;
  46         *top = rbnode->base_reg + rbnode->blklen - 1;
  47 }
  48
  49 static unsigned int regcache_rbtree_get_register(
  50         struct regcache_rbtree_node *rbnode, unsigned int idx,
  51         unsigned int word_size)
  52 {
  53         return regcache_get_val(rbnode->block, idx, word_size);
  54 }
  55
  56 static void regcache_rbtree_set_register(struct regcache_rbtree_node *rbnode,
  57                                          unsigned int idx, unsigned int val,
  58                                          unsigned int word_size)
  59 {
  60         regcache_set_val(rbnode->block, idx, val, word_size);
  61 }
  62
  63 static struct regcache_rbtree_node *regcache_rbtree_lookup(struct regmap *map,
  64         unsigned int reg)
  65 {
  66         struct regcache_rbtree_ctx *rbtree_ctx = map->cache;
  67         struct rb_node *node;
  68         struct regcache_rbtree_node *rbnode;
  69         unsigned int base_reg, top_reg;
  70
  71         rbnode = rbtree_ctx->cached_rbnode;
  72         if (rbnode) {
  73                 regcache_rbtree_get_base_top_reg(rbnode, &base_reg, &top_reg);
  74                 if (reg >= base_reg && reg <= top_reg)
  75                         return rbnode;
  76         }
  77
  78         node = rbtree_ctx->root.rb_node;
  79         while (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;
  84                         return rbnode;
  85                 } else if (reg > top_reg) {
  86                         node = node->rb_right;
  87                 } else if (reg < base_reg) {
  88                         node = node->rb_left;
  89                 }
  90         }
  91
  92         return NULL;
  93 }
  94
  95 static int regcache_rbtree_insert(struct rb_root *root,
  96                                   struct regcache_rbtree_node *rbnode)
  97 {
  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;
 102
 103         parent = NULL;
 104         new = &root->rb_node;
 105         while (*new) {
 106                 rbnode_tmp = container_of(*new, struct regcache_rbtree_node,
 107                                           node);
 108                 /* base and top registers of the current rbnode */
 109                 regcache_rbtree_get_base_top_reg(rbnode_tmp, &base_reg_tmp,
 110                                                  &top_reg_tmp);
 111                 /* base register of the rbnode to be added */
 112                 base_reg = rbnode->base_reg;
 113                 parent = *new;
 114                 /* if this register has already been inserted, just return */
 115                 if (base_reg >= base_reg_tmp &&
 116                     base_reg <= top_reg_tmp)
 117                         return 0;
 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);
 122         }
 123
 124         /* insert the node into the rbtree */
 125         rb_link_node(&rbnode->node, parent, new);
 126         rb_insert_color(&rbnode->node, root);
 127
 128         return 1;
 129 }
 130
 131 #ifdef CONFIG_DEBUG_FS
 132 static int rbtree_show(struct seq_file *s, void *ignored)
 133 {
 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;
 139         int nodes = 0;
 140         int registers = 0;
 141         int average;
 142
 143         mutex_lock(&map->lock);
 144
 145         for (node = rb_first(&rbtree_ctx->root); node != NULL;
 146              node = rb_next(node)) {
 147                 n = container_of(node, struct regcache_rbtree_node, node);
 148
 149                 regcache_rbtree_get_base_top_reg(n, &base, &top);
 150                 seq_printf(s, "%x-%x (%d)\n", base, top, top - base + 1);
 151
 152                 nodes++;
 153                 registers += top - base + 1;
 154         }
 155
 156         if (nodes)
 157                 average = registers / nodes;
 158         else
 159                 average = 0;
 160
 161         seq_printf(s, "%d nodes, %d registers, average %d registers\n",
 162                    nodes, registers, average);
 163
 164         mutex_unlock(&map->lock);
 165
 166         return 0;
 167 }
 168
 169 static int rbtree_open(struct inode *inode, struct file *file)
 170 {
 171         return single_open(file, rbtree_show, inode->i_private);
 172 }
 173
 174 static const struct file_operations rbtree_fops = {
 175         .open           = rbtree_open,
 176         .read           = seq_read,
 177         .llseek         = seq_lseek,
 178         .release        = single_release,
 179 };
 180
 181 static void rbtree_debugfs_init(struct regmap *map)
 182 {
 183         debugfs_create_file("rbtree", 0400, map->debugfs, map, &rbtree_fops);
 184 }
 185 #else
 186 static void rbtree_debugfs_init(struct regmap *map)
 187 {
 188 }
 189 #endif
 190
 191 static int regcache_rbtree_init(struct regmap *map)
 192 {
 193         struct regcache_rbtree_ctx *rbtree_ctx;
 194         int i;
 195         int ret;
 196
 197         map->cache = kmalloc(sizeof *rbtree_ctx, GFP_KERNEL);
 198         if (!map->cache)
 199                 return -ENOMEM;
 200
 201         rbtree_ctx = map->cache;
 202         rbtree_ctx->root = RB_ROOT;
 203         rbtree_ctx->cached_rbnode = NULL;
 204
 205         for (i = 0; i < map->num_reg_defaults; i++) {
 206                 ret = regcache_rbtree_write(map,
 207                                             map->reg_defaults[i].reg,
 208                                             map->reg_defaults[i].def);
 209                 if (ret)
 210                         goto err;
 211         }
 212
 213         rbtree_debugfs_init(map);
 214
 215         return 0;
 216
 217 err:
 218         regcache_rbtree_exit(map);
 219         return ret;
 220 }
 221
 222 static int regcache_rbtree_exit(struct regmap *map)
 223 {
 224         struct rb_node *next;
 225         struct regcache_rbtree_ctx *rbtree_ctx;
 226         struct regcache_rbtree_node *rbtree_node;
 227
 228         /* if we've already been called then just return */
 229         rbtree_ctx = map->cache;
 230         if (!rbtree_ctx)
 231                 return 0;
 232
 233         /* free up the rbtree */
 234         next = rb_first(&rbtree_ctx->root);
 235         while (next) {
 236                 rbtree_node = rb_entry(next, struct regcache_rbtree_node, node);
 237                 next = rb_next(&rbtree_node->node);
 238                 rb_erase(&rbtree_node->node, &rbtree_ctx->root);
 239                 kfree(rbtree_node->block);
 240                 kfree(rbtree_node);
 241         }
 242
 243         /* release the resources */
 244         kfree(map->cache);
 245         map->cache = NULL;
 246
 247         return 0;
 248 }
 249
 250 static int regcache_rbtree_read(struct regmap *map,
 251                                 unsigned int reg, unsigned int *value)
 252 {
 253         struct regcache_rbtree_node *rbnode;
 254         unsigned int reg_tmp;
 255
 256         rbnode = regcache_rbtree_lookup(map, reg);
 257         if (rbnode) {
 258                 reg_tmp = reg - rbnode->base_reg;
 259                 *value = regcache_rbtree_get_register(rbnode, reg_tmp,
 260                                                       map->cache_word_size);
 261         } else {
 262                 return -ENOENT;
 263         }
 264
 265         return 0;
 266 }
 267
 268
 269 static int regcache_rbtree_insert_to_block(struct regcache_rbtree_node *rbnode,
 270                                            unsigned int pos, unsigned int reg,
 271                                            unsigned int value, unsigned int word_size)
 272 {
 273         u8 *blk;
 274
 275         blk = krealloc(rbnode->block,
 276                        (rbnode->blklen + 1) * word_size, GFP_KERNEL);
 277         if (!blk)
 278                 return -ENOMEM;
 279
 280         /* insert the register value in the correct place in the rbnode block */
 281         memmove(blk + (pos + 1) * word_size,
 282                 blk + pos * word_size,
 283                 (rbnode->blklen - pos) * word_size);
 284
 285         /* update the rbnode block, its size and the base register */
 286         rbnode->block = blk;
 287         rbnode->blklen++;
 288         if (!pos)
 289                 rbnode->base_reg = reg;
 290
 291         regcache_rbtree_set_register(rbnode, pos, value, word_size);
 292         return 0;
 293 }
 294
 295 static int regcache_rbtree_write(struct regmap *map, unsigned int reg,
 296                                  unsigned int value)
 297 {
 298         struct regcache_rbtree_ctx *rbtree_ctx;
 299         struct regcache_rbtree_node *rbnode, *rbnode_tmp;
 300         struct rb_node *node;
 301         unsigned int val;
 302         unsigned int reg_tmp;
 303         unsigned int pos;
 304         int i;
 305         int ret;
 306
 307         rbtree_ctx = map->cache;
 308         /* if we can't locate it in the cached rbnode we'll have
 309          * to traverse the rbtree looking for it.
 310          */
 311         rbnode = regcache_rbtree_lookup(map, reg);
 312         if (rbnode) {
 313                 reg_tmp = reg - rbnode->base_reg;
 314                 val = regcache_rbtree_get_register(rbnode, reg_tmp,
 315                                                    map->cache_word_size);
 316                 if (val == value)
 317                         return 0;
 318                 regcache_rbtree_set_register(rbnode, reg_tmp, value,
 319                                              map->cache_word_size);
 320         } else {
 321                 /* look for an adjacent register to the one we are about to add */
 322                 for (node = rb_first(&rbtree_ctx->root); node;
 323                      node = rb_next(node)) {
 324                         rbnode_tmp = rb_entry(node, struct regcache_rbtree_node, node);
 325                         for (i = 0; i < rbnode_tmp->blklen; i++) {
 326                                 reg_tmp = rbnode_tmp->base_reg + i;
 327                                 if (abs(reg_tmp - reg) != 1)
 328                                         continue;
 329                                 /* decide where in the block to place our register */
 330                                 if (reg_tmp + 1 == reg)
 331                                         pos = i + 1;
 332                                 else
 333                                         pos = i;
 334                                 ret = regcache_rbtree_insert_to_block(rbnode_tmp, pos,
 335                                                                       reg, value,
 336                                                                       map->cache_word_size);
 337                                 if (ret)
 338                                         return ret;
 339                                 rbtree_ctx->cached_rbnode = rbnode_tmp;
 340                                 return 0;
 341                         }
 342                 }
 343                 /* we did not manage to find a place to insert it in an existing
 344                  * block so create a new rbnode with a single register in its block.
 345                  * This block will get populated further if any other adjacent
 346                  * registers get modified in the future.
 347                  */
 348                 rbnode = kzalloc(sizeof *rbnode, GFP_KERNEL);
 349                 if (!rbnode)
 350                         return -ENOMEM;
 351                 rbnode->blklen = 1;
 352                 rbnode->base_reg = reg;
 353                 rbnode->block = kmalloc(rbnode->blklen * map->cache_word_size,
 354                                         GFP_KERNEL);
 355                 if (!rbnode->block) {
 356                         kfree(rbnode);
 357                         return -ENOMEM;
 358                 }
 359                 regcache_rbtree_set_register(rbnode, 0, value, map->cache_word_size);
 360                 regcache_rbtree_insert(&rbtree_ctx->root, rbnode);
 361                 rbtree_ctx->cached_rbnode = rbnode;
 362         }
 363
 364         return 0;
 365 }
 366
 367 static int regcache_rbtree_sync(struct regmap *map, unsigned int min,
 368                                 unsigned int max)
 369 {
 370         struct regcache_rbtree_ctx *rbtree_ctx;
 371         struct rb_node *node;
 372         struct regcache_rbtree_node *rbnode;
 373         unsigned int regtmp;
 374         unsigned int val;
 375         int ret;
 376         int i, base, end;
 377
 378         rbtree_ctx = map->cache;
 379         for (node = rb_first(&rbtree_ctx->root); node; node = rb_next(node)) {
 380                 rbnode = rb_entry(node, struct regcache_rbtree_node, node);
 381
 382                 if (rbnode->base_reg < min)
 383                         continue;
 384                 if (rbnode->base_reg > max)
 385                         break;
 386                 if (rbnode->base_reg + rbnode->blklen < min)
 387                         continue;
 388
 389                 if (min > rbnode->base_reg)
 390                         base = min - rbnode->base_reg;
 391                 else
 392                         base = 0;
 393
 394                 if (max < rbnode->base_reg + rbnode->blklen)
 395                         end = rbnode->base_reg + rbnode->blklen - max;
 396                 else
 397                         end = rbnode->blklen;
 398
 399                 for (i = base; i < end; i++) {
 400                         regtmp = rbnode->base_reg + i;
 401                         val = regcache_rbtree_get_register(rbnode, i,
 402                                                            map->cache_word_size);
 403
 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)
 407                                 continue;
 408
 409                         map->cache_bypass = 1;
 410                         ret = _regmap_write(map, regtmp, val);
 411                         map->cache_bypass = 0;
 412                         if (ret)
 413                                 return ret;
 414                         dev_dbg(map->dev, "Synced register %#x, value %#x\n",
 415                                 regtmp, val);
 416                 }
 417         }
 418
 419         return 0;
 420 }
 421
 422 struct regcache_ops regcache_rbtree_ops = {
 423         .type = REGCACHE_RBTREE,
 424         .name = "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
 430 };