For review: issue 59 (fencepost related items)

[Dustin]

Branch is http://github.com/dustin/memcached/tree/issue59

I'd like someone to double-check my work here. I pulled in Mat's
suggestion, but wanted to understand more of why it hadn't actually
trigger. It seems that the actual limit was much lower.

Also, one particular thing I'd like to highlight is the following
modification I made as the number of items was changing:

- memset(itemstats, 0, sizeof(itemstats_t) * LARGEST_ID);
+ memset(itemstats, 0, sizeof(itemstats));

Logs:

commit c30737d0bbd46c7467fbe56f11a3b5bceea63b6f
Author: Dustin Sallings <dus...@spy.net>
Date: Mon Jun 22 00:23:48 2009 -0700

Kill off redundant and incorrect sizing definition.

It seems that in investigating the fencepost issue (issue59), it
was
revealed that the 255 value of LARGEST_ID was well beyond what was
ever possible to be referenced.

As actual value was limited to the POWER_LARGEST definition in
practice, I have LARGEST_ID use POWER_LARGEST to define itself.

commit c2f50759e7871b2aade88841c445873684fd134b
Author: Mat Hostetter <mjhos...@gmail.com>
Date: Mon Jun 22 00:06:58 2009 -0700

Clean up slab boundary checking.

http://groups.google.com/group/memcached/browse_thread/thread/45b70cced2c4bd

In items.c in memcached-1.2.8, these arrays allow indices up to
but
not including LARGEST_ID:

...
static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];

So this comment (which appears twice) is confused:

/* always true, warns: assert(it->slabs_clsid <= LARGEST_ID);
*/

The assert should be checking for clsid < LARGEST_ID, not <=. And
then the warning would go away. Or was the intent always to have
256
entries in the arrays, not 255?

Similarly, this code in items.c should be checking >=, not >, as
heads[LARGEST_ID] would be out-of-bounds:

if (slabs_clsid > LARGEST_ID) return NULL;
it = heads[slabs_clsid];

IMHO the confusion stems from the fact that LARGEST_ID is not
itself a
valid id, as the name seems to imply.




Complete diff from master:

diff --git a/items.c b/items.c
index 8d5046a..7c979a6 100644
--- a/items.c
+++ b/items.c
@@ -24,7 +24,7 @@ static void item_unlink_q(item *it);
*/
#define ITEM_UPDATE_INTERVAL 60

-#define LARGEST_ID 255
+#define LARGEST_ID POWER_LARGEST
typedef struct {
unsigned int evicted;
rel_time_t evicted_time;
@@ -39,7 +39,7 @@ static unsigned int sizes[LARGEST_ID];

void item_init(void) {
int i;
- memset(itemstats, 0, sizeof(itemstats_t) * LARGEST_ID);
+ memset(itemstats, 0, sizeof(itemstats));
for(i = 0; i < LARGEST_ID; i++) {
heads[i] = NULL;
tails[i] = NULL;
@@ -49,7 +49,7 @@ void item_init(void) {

void item_stats_reset(void) {
pthread_mutex_lock(&cache_lock);
- memset(itemstats, 0, sizeof(itemstats_t) * LARGEST_ID);
+ memset(itemstats, 0, sizeof(itemstats));
pthread_mutex_unlock(&cache_lock);
}

@@ -242,7 +242,7 @@ bool item_size_ok(const size_t nkey, const int
flags, const int nbytes) {

static void item_link_q(item *it) { /* item is the new head */
item **head, **tail;
- /* always true, warns: assert(it->slabs_clsid <= LARGEST_ID); */
+ assert(it->slabs_clsid < LARGEST_ID);
assert((it->it_flags & ITEM_SLABBED) == 0);

head = &heads[it->slabs_clsid];
@@ -260,7 +260,7 @@ static void item_link_q(item *it) { /* item is the
new head */

static void item_unlink_q(item *it) {
item **head, **tail;
- /* always true, warns: assert(it->slabs_clsid <= LARGEST_ID); */
+ assert(it->slabs_clsid < LARGEST_ID);
head = &heads[it->slabs_clsid];
tail = &tails[it->slabs_clsid];

@@ -362,7 +362,7 @@ char *do_item_cachedump(const unsigned int
slabs_clsid, const unsigned int limit
char key_temp[KEY_MAX_LENGTH + 1];
char temp[512];

- if (slabs_clsid > LARGEST_ID) return NULL;
+ if (slabs_clsid >= LARGEST_ID) return NULL;
it = heads[slabs_clsid];

buffer = malloc((size_t)memlimit);

[Trond Norbye]

Hi, I just looked through the diff, and have the following comments:

Dustin wrote:
> Complete diff from master:
>
> diff --git a/items.c b/items.c
> index 8d5046a..7c979a6 100644
> --- a/items.c
> +++ b/items.c
> @@ -24,7 +24,7 @@ static void item_unlink_q(item *it);
> */
> #define ITEM_UPDATE_INTERVAL 60
>
> -#define LARGEST_ID 255
> +#define LARGEST_ID POWER_LARGEST
>

Some time in the future this should be only one constant... It is just
confusing to have two different names for the same thing (but that
should be done in it's own commit)...

> typedef struct {
> unsigned int evicted;
> rel_time_t evicted_time;
> @@ -39,7 +39,7 @@ static unsigned int sizes[LARGEST_ID];
>
> void item_init(void) {
> int i;
> - memset(itemstats, 0, sizeof(itemstats_t) * LARGEST_ID);
> + memset(itemstats, 0, sizeof(itemstats));
> for(i = 0; i < LARGEST_ID; i++) {
> heads[i] = NULL;
> tails[i] = NULL;
> @@ -49,7 +49,7 @@ void item_init(void) {
>
>

A better solution would be to just nuke the complete function. It is
only called from main, and all it does is to zero out global variables.
(Global variables are always set to zero if they aren't given any other
values).

Trond