* [PATCH 1/2] ASoC: soc-cache: block based rbtree compression
@ 2011-05-02 12:26 Dimitris Papastamos
2011-05-02 12:26 ` [PATCH 2/2] ASoC: soc-cache: cache a pointer to the last accessed rbtree block Dimitris Papastamos
0 siblings, 1 reply; 2+ messages in thread
From: Dimitris Papastamos @ 2011-05-02 12:26 UTC (permalink / raw)
To: Mark Brown, Liam Girdwood; +Cc: alsa-devel, patches, Liam Girdwood
This patch prepares the ground for the actual rbtree optimization patch
which will save a pointer to the last accessed register block that was used
in either the read() or write() functions.
Each node manages a block of up to RBTREE_BLOCK_NUM registers. There can be
no two nodes with overlapping blocks. Currently there is no check in the code
to scream in case that ever happens. Each block has a base and top register,
all others lie in between these registers. Note that variable length blocks
aren't supported. So if you have an interval [8, 15] and only some of those
registers actually exist on the device, the block will have the non-existent
registers as zero. There is also no way of reporting that any of those
non-existent registers were accessed/modified.
The larger the block size, the more probable it is that one of the
managed registers is non-zero, and therefore the node will need to be
allocated at initialization time and waste space.
If register N is accessed and it is not part of any of the current
blocks in the rbtree, a new node is created with a base register
which is floor(N / RBTREE_BLOCK_NUM) * RBTREE_BLOCK_NUM and a top
register as base_register + RBTREE_BLOCK_NUM - 1. All other registers
in the block are initialized as expected and the node is inserted into
the tree.
Signed-off-by: Dimitris Papastamos <dp@opensource.wolfsonmicro.com>
---
sound/soc/soc-cache.c | 177 +++++++++++++++++++++++++++++++++++--------------
1 files changed, 128 insertions(+), 49 deletions(-)
diff --git a/sound/soc/soc-cache.c b/sound/soc/soc-cache.c
index a217db2..c518b6e 100644
--- a/sound/soc/soc-cache.c
+++ b/sound/soc/soc-cache.c
@@ -593,32 +593,58 @@ static unsigned int snd_soc_get_cache_val(const void *base, unsigned int idx,
return -1;
}
-struct snd_soc_rbtree_node {
- struct rb_node node;
+struct snd_soc_rbtree_reg_blk {
unsigned int reg;
unsigned int value;
unsigned int defval;
} __attribute__ ((packed));
+#define RBTREE_BLOCK_NUM 32
+struct snd_soc_rbtree_node {
+ struct rb_node node;
+ struct snd_soc_rbtree_reg_blk block[RBTREE_BLOCK_NUM];
+ unsigned int blklen;
+} __attribute__ ((packed));
+
struct snd_soc_rbtree_ctx {
struct rb_root root;
};
+static inline int snd_soc_rbtree_block_count(void)
+{
+ return RBTREE_BLOCK_NUM;
+}
+
+static inline struct snd_soc_rbtree_reg_blk *snd_soc_rbtree_base_block(
+ struct snd_soc_rbtree_node *rbnode)
+{
+ return &rbnode->block[0];
+}
+
+static inline struct snd_soc_rbtree_reg_blk *snd_soc_rbtree_top_block(
+ struct snd_soc_rbtree_node *rbnode)
+{
+ return &rbnode->block[snd_soc_rbtree_block_count() - 1];
+}
+
static struct snd_soc_rbtree_node *snd_soc_rbtree_lookup(
struct rb_root *root, unsigned int reg)
{
struct rb_node *node;
struct snd_soc_rbtree_node *rbnode;
+ struct snd_soc_rbtree_reg_blk *baseblk, *topblk;
node = root->rb_node;
while (node) {
rbnode = container_of(node, struct snd_soc_rbtree_node, node);
- if (rbnode->reg < reg)
- node = node->rb_left;
- else if (rbnode->reg > reg)
- node = node->rb_right;
- else
+ baseblk = snd_soc_rbtree_base_block(rbnode);
+ topblk = snd_soc_rbtree_top_block(rbnode);
+ if (reg >= baseblk->reg && reg <= topblk->reg)
return rbnode;
+ else if (reg > topblk->reg)
+ node = node->rb_right;
+ else if (reg < baseblk->reg)
+ node = node->rb_left;
}
return NULL;
@@ -629,19 +655,28 @@ static int snd_soc_rbtree_insert(struct rb_root *root,
{
struct rb_node **new, *parent;
struct snd_soc_rbtree_node *rbnode_tmp;
+ struct snd_soc_rbtree_reg_blk *baseblk_tmp, *topblk_tmp;
+ struct snd_soc_rbtree_reg_blk *baseblk;
parent = NULL;
new = &root->rb_node;
while (*new) {
rbnode_tmp = container_of(*new, struct snd_soc_rbtree_node,
node);
+ /* base and top blocks of the current rbnode */
+ baseblk_tmp = snd_soc_rbtree_base_block(rbnode_tmp);
+ topblk_tmp = snd_soc_rbtree_top_block(rbnode_tmp);
+ /* base block of the rbnode to be added */
+ baseblk = snd_soc_rbtree_base_block(rbnode);
parent = *new;
- if (rbnode_tmp->reg < rbnode->reg)
- new = &((*new)->rb_left);
- else if (rbnode_tmp->reg > rbnode->reg)
- new = &((*new)->rb_right);
- else
+ /* if this block has already been inserted, just return */
+ if (baseblk->reg >= baseblk_tmp->reg &&
+ baseblk->reg <= topblk_tmp->reg)
return 0;
+ else if (baseblk->reg > topblk_tmp->reg)
+ new = &((*new)->rb_right);
+ else if (baseblk->reg < baseblk_tmp->reg)
+ new = &((*new)->rb_left);
}
/* insert the node into the rbtree */
@@ -656,26 +691,31 @@ static int snd_soc_rbtree_cache_sync(struct snd_soc_codec *codec)
struct snd_soc_rbtree_ctx *rbtree_ctx;
struct rb_node *node;
struct snd_soc_rbtree_node *rbnode;
- unsigned int val;
+ struct snd_soc_rbtree_reg_blk *regblk;
+ unsigned int val, i;
int ret;
rbtree_ctx = codec->reg_cache;
+ /* for each node sync all its blocks */
for (node = rb_first(&rbtree_ctx->root); node; node = rb_next(node)) {
rbnode = rb_entry(node, struct snd_soc_rbtree_node, node);
- if (rbnode->value == rbnode->defval)
- continue;
- WARN_ON(codec->writable_register &&
- codec->writable_register(codec, rbnode->reg));
- ret = snd_soc_cache_read(codec, rbnode->reg, &val);
- if (ret)
- return ret;
- codec->cache_bypass = 1;
- ret = snd_soc_write(codec, rbnode->reg, val);
- codec->cache_bypass = 0;
- if (ret)
- return ret;
- dev_dbg(codec->dev, "Synced register %#x, value = %#x\n",
- rbnode->reg, val);
+ for (i = 0; i < rbnode->blklen; ++i) {
+ regblk = &rbnode->block[i];
+ if (regblk->value == regblk->defval)
+ continue;
+ WARN_ON(codec->writable_register &&
+ codec->writable_register(codec, regblk->reg));
+ ret = snd_soc_cache_read(codec, regblk->reg, &val);
+ if (ret)
+ return ret;
+ codec->cache_bypass = 1;
+ ret = snd_soc_write(codec, regblk->reg, val);
+ codec->cache_bypass = 0;
+ if (ret)
+ return ret;
+ dev_dbg(codec->dev, "Synced register %#x, value = %#x\n",
+ regblk->reg, val);
+ }
}
return 0;
@@ -686,27 +726,40 @@ static int snd_soc_rbtree_cache_write(struct snd_soc_codec *codec,
{
struct snd_soc_rbtree_ctx *rbtree_ctx;
struct snd_soc_rbtree_node *rbnode;
+ struct snd_soc_rbtree_reg_blk *regblk;
+ struct snd_soc_rbtree_reg_blk *baseblk;
+ unsigned int base_reg;
+ int blkcount, i;
rbtree_ctx = codec->reg_cache;
rbnode = snd_soc_rbtree_lookup(&rbtree_ctx->root, reg);
if (rbnode) {
- if (rbnode->value == value)
+ baseblk = snd_soc_rbtree_base_block(rbnode);
+ regblk = &rbnode->block[reg - baseblk->reg];
+ if (regblk->value == value)
return 0;
- rbnode->value = value;
+ regblk->value = value;
} else {
/* bail out early, no need to create the rbnode yet */
if (!value)
return 0;
/*
- * for uninitialized registers whose value is changed
- * from the default zero, create an rbnode and insert
- * it into the tree.
+ * if the value of any of the uninitialized registers in a
+ * block is changed from the default zero, create an rbnode
+ * and insert it into the tree. Make sure to initialize all
+ * the registers in the block.
*/
rbnode = kzalloc(sizeof *rbnode, GFP_KERNEL);
if (!rbnode)
return -ENOMEM;
- rbnode->reg = reg;
- rbnode->value = value;
+ blkcount = snd_soc_rbtree_block_count();
+ base_reg = (reg / blkcount) * blkcount;
+ for (i = 0; i < blkcount; ++i) {
+ regblk = &rbnode->block[i];
+ regblk->reg = base_reg + i;
+ if (regblk->reg == reg)
+ regblk->value = value;
+ }
snd_soc_rbtree_insert(&rbtree_ctx->root, rbnode);
}
@@ -718,11 +771,13 @@ static int snd_soc_rbtree_cache_read(struct snd_soc_codec *codec,
{
struct snd_soc_rbtree_ctx *rbtree_ctx;
struct snd_soc_rbtree_node *rbnode;
+ struct snd_soc_rbtree_reg_blk *baseblk;
rbtree_ctx = codec->reg_cache;
rbnode = snd_soc_rbtree_lookup(&rbtree_ctx->root, reg);
if (rbnode) {
- *value = rbnode->value;
+ baseblk = snd_soc_rbtree_base_block(rbnode);
+ *value = rbnode->block[reg - baseblk->reg].value;
} else {
/* uninitialized registers default to 0 */
*value = 0;
@@ -762,10 +817,13 @@ static int snd_soc_rbtree_cache_init(struct snd_soc_codec *codec)
{
struct snd_soc_rbtree_node *rbtree_node;
struct snd_soc_rbtree_ctx *rbtree_ctx;
- unsigned int val;
+ unsigned int reg, val;
unsigned int word_size;
- int i;
+ int i, j;
int ret;
+ int blkcount;
+ int numblocks;
+ int flag;
codec->reg_cache = kmalloc(sizeof *rbtree_ctx, GFP_KERNEL);
if (!codec->reg_cache)
@@ -777,28 +835,49 @@ static int snd_soc_rbtree_cache_init(struct snd_soc_codec *codec)
if (!codec->reg_def_copy)
return 0;
- /*
- * populate the rbtree with the initialized registers. All other
- * registers will be inserted when they are first modified.
- */
word_size = codec->driver->reg_word_size;
- for (i = 0; i < codec->driver->reg_cache_size; ++i) {
- val = snd_soc_get_cache_val(codec->reg_def_copy, i, word_size);
- if (!val)
+ blkcount = snd_soc_rbtree_block_count();
+ numblocks = (codec->driver->reg_cache_size - 1 + blkcount) / blkcount;
+ for (i = 0; i < numblocks; ++i) {
+ /* check if a block is comprised of uninitialized registers only */
+ for (j = 0, flag = 0; j < blkcount; ++j) {
+ reg = i * blkcount + j;
+ if (reg >= codec->driver->reg_cache_size)
+ break;
+ val = snd_soc_get_cache_val(codec->reg_def_copy,
+ reg, word_size);
+ if (val) {
+ flag = 1;
+ break;
+ }
+ }
+ /* ignore this block until one of its registers is modified */
+ if (!flag)
continue;
rbtree_node = kzalloc(sizeof *rbtree_node, GFP_KERNEL);
if (!rbtree_node) {
ret = -ENOMEM;
- snd_soc_cache_exit(codec);
- break;
+ goto err;
+ }
+ /* initialize the register block */
+ for (j = 0; j < blkcount; ++j) {
+ reg = i * blkcount + j;
+ if (reg >= codec->driver->reg_cache_size)
+ break;
+ val = snd_soc_get_cache_val(codec->reg_def_copy, reg, word_size);
+ rbtree_node->block[j].reg = reg;
+ rbtree_node->block[j].value = val;
+ rbtree_node->block[j].defval = val;
}
- rbtree_node->reg = i;
- rbtree_node->value = val;
- rbtree_node->defval = val;
+ rbtree_node->blklen = j;
snd_soc_rbtree_insert(&rbtree_ctx->root, rbtree_node);
}
return 0;
+
+err:
+ snd_soc_cache_exit(codec);
+ return ret;
}
#ifdef CONFIG_SND_SOC_CACHE_LZO
--
1.7.5
^ permalink raw reply related [flat|nested] 2+ messages in thread
* [PATCH 2/2] ASoC: soc-cache: cache a pointer to the last accessed rbtree block
2011-05-02 12:26 [PATCH 1/2] ASoC: soc-cache: block based rbtree compression Dimitris Papastamos
@ 2011-05-02 12:26 ` Dimitris Papastamos
0 siblings, 0 replies; 2+ messages in thread
From: Dimitris Papastamos @ 2011-05-02 12:26 UTC (permalink / raw)
To: Mark Brown, Liam Girdwood; +Cc: alsa-devel, patches, Liam Girdwood
Whenever we are doing a read or a write through the rbtree code, we'll
cache the a pointer to the register block. To avoid looking up the register
everytime we do a read or a write, we first check if it can be found in
the cached register block, otherwise we go through the slow path and in the
end we cache the pointer to the register block.
Signed-off-by: Dimitris Papastamos <dp@opensource.wolfsonmicro.com>
---
sound/soc/soc-cache.c | 34 ++++++++++++++++++++++++++++++++--
1 files changed, 32 insertions(+), 2 deletions(-)
diff --git a/sound/soc/soc-cache.c b/sound/soc/soc-cache.c
index c518b6e..09048ea 100644
--- a/sound/soc/soc-cache.c
+++ b/sound/soc/soc-cache.c
@@ -608,6 +608,7 @@ struct snd_soc_rbtree_node {
struct snd_soc_rbtree_ctx {
struct rb_root root;
+ struct snd_soc_rbtree_node *cached_rbnode;
};
static inline int snd_soc_rbtree_block_count(void)
@@ -727,11 +728,25 @@ static int snd_soc_rbtree_cache_write(struct snd_soc_codec *codec,
struct snd_soc_rbtree_ctx *rbtree_ctx;
struct snd_soc_rbtree_node *rbnode;
struct snd_soc_rbtree_reg_blk *regblk;
- struct snd_soc_rbtree_reg_blk *baseblk;
+ struct snd_soc_rbtree_reg_blk *baseblk, *topblk;
unsigned int base_reg;
int blkcount, i;
rbtree_ctx = codec->reg_cache;
+ /* handle cached write */
+ rbnode = rbtree_ctx->cached_rbnode;
+ if (rbnode) {
+ baseblk = snd_soc_rbtree_base_block(rbnode);
+ topblk = snd_soc_rbtree_top_block(rbnode);
+ if (reg >= baseblk->reg && reg <= topblk->reg) {
+ regblk = &rbnode->block[reg - baseblk->reg];
+ if (regblk->value == value)
+ return 0;
+ regblk->value = value;
+ return 0;
+ }
+ }
+ /* if not cached, look it up in the rbtree and cache it */
rbnode = snd_soc_rbtree_lookup(&rbtree_ctx->root, reg);
if (rbnode) {
baseblk = snd_soc_rbtree_base_block(rbnode);
@@ -739,6 +754,7 @@ static int snd_soc_rbtree_cache_write(struct snd_soc_codec *codec,
if (regblk->value == value)
return 0;
regblk->value = value;
+ rbtree_ctx->cached_rbnode = rbnode;
} else {
/* bail out early, no need to create the rbnode yet */
if (!value)
@@ -761,6 +777,7 @@ static int snd_soc_rbtree_cache_write(struct snd_soc_codec *codec,
regblk->value = value;
}
snd_soc_rbtree_insert(&rbtree_ctx->root, rbnode);
+ rbtree_ctx->cached_rbnode = rbnode;
}
return 0;
@@ -771,13 +788,25 @@ static int snd_soc_rbtree_cache_read(struct snd_soc_codec *codec,
{
struct snd_soc_rbtree_ctx *rbtree_ctx;
struct snd_soc_rbtree_node *rbnode;
- struct snd_soc_rbtree_reg_blk *baseblk;
+ struct snd_soc_rbtree_reg_blk *baseblk, *topblk;
rbtree_ctx = codec->reg_cache;
+ /* handle cached read */
+ rbnode = rbtree_ctx->cached_rbnode;
+ if (rbnode) {
+ baseblk = snd_soc_rbtree_base_block(rbnode);
+ topblk = snd_soc_rbtree_top_block(rbnode);
+ if (reg >= baseblk->reg && reg <= topblk->reg) {
+ *value = rbnode->block[reg - baseblk->reg].value;
+ return 0;
+ }
+ }
+ /* if not cached, look it up in the rbtree and cache it */
rbnode = snd_soc_rbtree_lookup(&rbtree_ctx->root, reg);
if (rbnode) {
baseblk = snd_soc_rbtree_base_block(rbnode);
*value = rbnode->block[reg - baseblk->reg].value;
+ rbtree_ctx->cached_rbnode = rbnode;
} else {
/* uninitialized registers default to 0 */
*value = 0;
@@ -831,6 +860,7 @@ static int snd_soc_rbtree_cache_init(struct snd_soc_codec *codec)
rbtree_ctx = codec->reg_cache;
rbtree_ctx->root = RB_ROOT;
+ rbtree_ctx->cached_rbnode = NULL;
if (!codec->reg_def_copy)
return 0;
--
1.7.5
^ permalink raw reply related [flat|nested] 2+ messages in thread
end of thread, other threads:[~2011-05-02 12:26 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2011-05-02 12:26 [PATCH 1/2] ASoC: soc-cache: block based rbtree compression Dimitris Papastamos
2011-05-02 12:26 ` [PATCH 2/2] ASoC: soc-cache: cache a pointer to the last accessed rbtree block Dimitris Papastamos
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).