← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-lowlatency/precise

« back to all changes in this revision

Viewing changes to drivers/base/regmap/regcache-rbtree.c

  • Committer: Package Import Robot
  • Author(s): Alessio Igor Bogani
  • Date: 2011-10-26 11:13:05 UTC
  • Revision ID: package-import@ubuntu.com-20111026111305-tz023xykf0i6eosh
Tags: upstream-3.2.0
Import upstream version 3.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
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/rbtree.h>
 
15
 
 
16
#include "internal.h"
 
17
 
 
18
static int regcache_rbtree_write(struct regmap *map, unsigned int reg,
 
19
                                 unsigned int value);
 
20
 
 
21
struct regcache_rbtree_node {
 
22
        /* the actual rbtree node holding this block */
 
23
        struct rb_node node;
 
24
        /* base register handled by this block */
 
25
        unsigned int base_reg;
 
26
        /* block of adjacent registers */
 
27
        void *block;
 
28
        /* number of registers available in the block */
 
29
        unsigned int blklen;
 
30
} __attribute__ ((packed));
 
31
 
 
32
struct regcache_rbtree_ctx {
 
33
        struct rb_root root;
 
34
        struct regcache_rbtree_node *cached_rbnode;
 
35
};
 
36
 
 
37
static inline void regcache_rbtree_get_base_top_reg(
 
38
        struct regcache_rbtree_node *rbnode,
 
39
        unsigned int *base, unsigned int *top)
 
40
{
 
41
        *base = rbnode->base_reg;
 
42
        *top = rbnode->base_reg + rbnode->blklen - 1;
 
43
}
 
44
 
 
45
static unsigned int regcache_rbtree_get_register(
 
46
        struct regcache_rbtree_node *rbnode, unsigned int idx,
 
47
        unsigned int word_size)
 
48
{
 
49
        return regcache_get_val(rbnode->block, idx, word_size);
 
50
}
 
51
 
 
52
static void regcache_rbtree_set_register(struct regcache_rbtree_node *rbnode,
 
53
                                         unsigned int idx, unsigned int val,
 
54
                                         unsigned int word_size)
 
55
{
 
56
        regcache_set_val(rbnode->block, idx, val, word_size);
 
57
}
 
58
 
 
59
static struct regcache_rbtree_node *regcache_rbtree_lookup(struct regmap *map,
 
60
        unsigned int reg)
 
61
{
 
62
        struct regcache_rbtree_ctx *rbtree_ctx = map->cache;
 
63
        struct rb_node *node;
 
64
        struct regcache_rbtree_node *rbnode;
 
65
        unsigned int base_reg, top_reg;
 
66
 
 
67
        rbnode = rbtree_ctx->cached_rbnode;
 
68
        if (rbnode) {
 
69
                regcache_rbtree_get_base_top_reg(rbnode, &base_reg, &top_reg);
 
70
                if (reg >= base_reg && reg <= top_reg)
 
71
                        return rbnode;
 
72
        }
 
73
 
 
74
        node = rbtree_ctx->root.rb_node;
 
75
        while (node) {
 
76
                rbnode = container_of(node, struct regcache_rbtree_node, node);
 
77
                regcache_rbtree_get_base_top_reg(rbnode, &base_reg, &top_reg);
 
78
                if (reg >= base_reg && reg <= top_reg) {
 
79
                        rbtree_ctx->cached_rbnode = rbnode;
 
80
                        return rbnode;
 
81
                } else if (reg > top_reg) {
 
82
                        node = node->rb_right;
 
83
                } else if (reg < base_reg) {
 
84
                        node = node->rb_left;
 
85
                }
 
86
        }
 
87
 
 
88
        return NULL;
 
89
}
 
90
 
 
91
static int regcache_rbtree_insert(struct rb_root *root,
 
92
                                  struct regcache_rbtree_node *rbnode)
 
93
{
 
94
        struct rb_node **new, *parent;
 
95
        struct regcache_rbtree_node *rbnode_tmp;
 
96
        unsigned int base_reg_tmp, top_reg_tmp;
 
97
        unsigned int base_reg;
 
98
 
 
99
        parent = NULL;
 
100
        new = &root->rb_node;
 
101
        while (*new) {
 
102
                rbnode_tmp = container_of(*new, struct regcache_rbtree_node,
 
103
                                          node);
 
104
                /* base and top registers of the current rbnode */
 
105
                regcache_rbtree_get_base_top_reg(rbnode_tmp, &base_reg_tmp,
 
106
                                                 &top_reg_tmp);
 
107
                /* base register of the rbnode to be added */
 
108
                base_reg = rbnode->base_reg;
 
109
                parent = *new;
 
110
                /* if this register has already been inserted, just return */
 
111
                if (base_reg >= base_reg_tmp &&
 
112
                    base_reg <= top_reg_tmp)
 
113
                        return 0;
 
114
                else if (base_reg > top_reg_tmp)
 
115
                        new = &((*new)->rb_right);
 
116
                else if (base_reg < base_reg_tmp)
 
117
                        new = &((*new)->rb_left);
 
118
        }
 
119
 
 
120
        /* insert the node into the rbtree */
 
121
        rb_link_node(&rbnode->node, parent, new);
 
122
        rb_insert_color(&rbnode->node, root);
 
123
 
 
124
        return 1;
 
125
}
 
126
 
 
127
static int regcache_rbtree_init(struct regmap *map)
 
128
{
 
129
        struct regcache_rbtree_ctx *rbtree_ctx;
 
130
        int i;
 
131
        int ret;
 
132
 
 
133
        map->cache = kmalloc(sizeof *rbtree_ctx, GFP_KERNEL);
 
134
        if (!map->cache)
 
135
                return -ENOMEM;
 
136
 
 
137
        rbtree_ctx = map->cache;
 
138
        rbtree_ctx->root = RB_ROOT;
 
139
        rbtree_ctx->cached_rbnode = NULL;
 
140
 
 
141
        for (i = 0; i < map->num_reg_defaults; i++) {
 
142
                ret = regcache_rbtree_write(map,
 
143
                                            map->reg_defaults[i].reg,
 
144
                                            map->reg_defaults[i].def);
 
145
                if (ret)
 
146
                        goto err;
 
147
        }
 
148
 
 
149
        return 0;
 
150
 
 
151
err:
 
152
        regcache_exit(map);
 
153
        return ret;
 
154
}
 
155
 
 
156
static int regcache_rbtree_exit(struct regmap *map)
 
157
{
 
158
        struct rb_node *next;
 
159
        struct regcache_rbtree_ctx *rbtree_ctx;
 
160
        struct regcache_rbtree_node *rbtree_node;
 
161
 
 
162
        /* if we've already been called then just return */
 
163
        rbtree_ctx = map->cache;
 
164
        if (!rbtree_ctx)
 
165
                return 0;
 
166
 
 
167
        /* free up the rbtree */
 
168
        next = rb_first(&rbtree_ctx->root);
 
169
        while (next) {
 
170
                rbtree_node = rb_entry(next, struct regcache_rbtree_node, node);
 
171
                next = rb_next(&rbtree_node->node);
 
172
                rb_erase(&rbtree_node->node, &rbtree_ctx->root);
 
173
                kfree(rbtree_node->block);
 
174
                kfree(rbtree_node);
 
175
        }
 
176
 
 
177
        /* release the resources */
 
178
        kfree(map->cache);
 
179
        map->cache = NULL;
 
180
 
 
181
        return 0;
 
182
}
 
183
 
 
184
static int regcache_rbtree_read(struct regmap *map,
 
185
                                unsigned int reg, unsigned int *value)
 
186
{
 
187
        struct regcache_rbtree_node *rbnode;
 
188
        unsigned int reg_tmp;
 
189
 
 
190
        rbnode = regcache_rbtree_lookup(map, reg);
 
191
        if (rbnode) {
 
192
                reg_tmp = reg - rbnode->base_reg;
 
193
                *value = regcache_rbtree_get_register(rbnode, reg_tmp,
 
194
                                                      map->cache_word_size);
 
195
        } else {
 
196
                return -ENOENT;
 
197
        }
 
198
 
 
199
        return 0;
 
200
}
 
201
 
 
202
 
 
203
static int regcache_rbtree_insert_to_block(struct regcache_rbtree_node *rbnode,
 
204
                                           unsigned int pos, unsigned int reg,
 
205
                                           unsigned int value, unsigned int word_size)
 
206
{
 
207
        u8 *blk;
 
208
 
 
209
        blk = krealloc(rbnode->block,
 
210
                       (rbnode->blklen + 1) * word_size, GFP_KERNEL);
 
211
        if (!blk)
 
212
                return -ENOMEM;
 
213
 
 
214
        /* insert the register value in the correct place in the rbnode block */
 
215
        memmove(blk + (pos + 1) * word_size,
 
216
                blk + pos * word_size,
 
217
                (rbnode->blklen - pos) * word_size);
 
218
 
 
219
        /* update the rbnode block, its size and the base register */
 
220
        rbnode->block = blk;
 
221
        rbnode->blklen++;
 
222
        if (!pos)
 
223
                rbnode->base_reg = reg;
 
224
 
 
225
        regcache_rbtree_set_register(rbnode, pos, value, word_size);
 
226
        return 0;
 
227
}
 
228
 
 
229
static int regcache_rbtree_write(struct regmap *map, unsigned int reg,
 
230
                                 unsigned int value)
 
231
{
 
232
        struct regcache_rbtree_ctx *rbtree_ctx;
 
233
        struct regcache_rbtree_node *rbnode, *rbnode_tmp;
 
234
        struct rb_node *node;
 
235
        unsigned int val;
 
236
        unsigned int reg_tmp;
 
237
        unsigned int pos;
 
238
        int i;
 
239
        int ret;
 
240
 
 
241
        rbtree_ctx = map->cache;
 
242
        /* if we can't locate it in the cached rbnode we'll have
 
243
         * to traverse the rbtree looking for it.
 
244
         */
 
245
        rbnode = regcache_rbtree_lookup(map, reg);
 
246
        if (rbnode) {
 
247
                reg_tmp = reg - rbnode->base_reg;
 
248
                val = regcache_rbtree_get_register(rbnode, reg_tmp,
 
249
                                                   map->cache_word_size);
 
250
                if (val == value)
 
251
                        return 0;
 
252
                regcache_rbtree_set_register(rbnode, reg_tmp, value,
 
253
                                             map->cache_word_size);
 
254
        } else {
 
255
                /* look for an adjacent register to the one we are about to add */
 
256
                for (node = rb_first(&rbtree_ctx->root); node;
 
257
                     node = rb_next(node)) {
 
258
                        rbnode_tmp = rb_entry(node, struct regcache_rbtree_node, node);
 
259
                        for (i = 0; i < rbnode_tmp->blklen; i++) {
 
260
                                reg_tmp = rbnode_tmp->base_reg + i;
 
261
                                if (abs(reg_tmp - reg) != 1)
 
262
                                        continue;
 
263
                                /* decide where in the block to place our register */
 
264
                                if (reg_tmp + 1 == reg)
 
265
                                        pos = i + 1;
 
266
                                else
 
267
                                        pos = i;
 
268
                                ret = regcache_rbtree_insert_to_block(rbnode_tmp, pos,
 
269
                                                                      reg, value,
 
270
                                                                      map->cache_word_size);
 
271
                                if (ret)
 
272
                                        return ret;
 
273
                                rbtree_ctx->cached_rbnode = rbnode_tmp;
 
274
                                return 0;
 
275
                        }
 
276
                }
 
277
                /* we did not manage to find a place to insert it in an existing
 
278
                 * block so create a new rbnode with a single register in its block.
 
279
                 * This block will get populated further if any other adjacent
 
280
                 * registers get modified in the future.
 
281
                 */
 
282
                rbnode = kzalloc(sizeof *rbnode, GFP_KERNEL);
 
283
                if (!rbnode)
 
284
                        return -ENOMEM;
 
285
                rbnode->blklen = 1;
 
286
                rbnode->base_reg = reg;
 
287
                rbnode->block = kmalloc(rbnode->blklen * map->cache_word_size,
 
288
                                        GFP_KERNEL);
 
289
                if (!rbnode->block) {
 
290
                        kfree(rbnode);
 
291
                        return -ENOMEM;
 
292
                }
 
293
                regcache_rbtree_set_register(rbnode, 0, value, map->cache_word_size);
 
294
                regcache_rbtree_insert(&rbtree_ctx->root, rbnode);
 
295
                rbtree_ctx->cached_rbnode = rbnode;
 
296
        }
 
297
 
 
298
        return 0;
 
299
}
 
300
 
 
301
static int regcache_rbtree_sync(struct regmap *map)
 
302
{
 
303
        struct regcache_rbtree_ctx *rbtree_ctx;
 
304
        struct rb_node *node;
 
305
        struct regcache_rbtree_node *rbnode;
 
306
        unsigned int regtmp;
 
307
        unsigned int val;
 
308
        int ret;
 
309
        int i;
 
310
 
 
311
        rbtree_ctx = map->cache;
 
312
        for (node = rb_first(&rbtree_ctx->root); node; node = rb_next(node)) {
 
313
                rbnode = rb_entry(node, struct regcache_rbtree_node, node);
 
314
                for (i = 0; i < rbnode->blklen; i++) {
 
315
                        regtmp = rbnode->base_reg + i;
 
316
                        val = regcache_rbtree_get_register(rbnode, i,
 
317
                                                           map->cache_word_size);
 
318
 
 
319
                        /* Is this the hardware default?  If so skip. */
 
320
                        ret = regcache_lookup_reg(map, i);
 
321
                        if (ret > 0 && val == map->reg_defaults[ret].def)
 
322
                                continue;
 
323
 
 
324
                        map->cache_bypass = 1;
 
325
                        ret = _regmap_write(map, regtmp, val);
 
326
                        map->cache_bypass = 0;
 
327
                        if (ret)
 
328
                                return ret;
 
329
                        dev_dbg(map->dev, "Synced register %#x, value %#x\n",
 
330
                                regtmp, val);
 
331
                }
 
332
        }
 
333
 
 
334
        return 0;
 
335
}
 
336
 
 
337
struct regcache_ops regcache_rbtree_ops = {
 
338
        .type = REGCACHE_RBTREE,
 
339
        .name = "rbtree",
 
340
        .init = regcache_rbtree_init,
 
341
        .exit = regcache_rbtree_exit,
 
342
        .read = regcache_rbtree_read,
 
343
        .write = regcache_rbtree_write,
 
344
        .sync = regcache_rbtree_sync
 
345
};