Comments on research!rsc: Using Uninitialized Memory for Fun and Profit

At first I thought it's going to be a virtual memo...

2008-04-08T02:40:00.000-04:00

At first I thought it's going to be a virtual memory trick. But no.
Well, actually, it could be. This reminds me of copying garbage collectors which also trade more space usage for less time allocating, and the algorithms when stripped of all the complexity have the same gist as those in the article.

Actually, I'm wrong. It's the declaration for ele...

2008-03-16T23:46:00.000-04:00

Actually, I'm wrong. It's the declaration for elements in sparse[] that must be unsigned. Bah.

@rsc i can be unsigned all day -- it's n that must...

2008-03-16T14:51:00.000-04:00

@rsc i can be unsigned all day -- it's n that must be unsigned :) The problem is when you dereference sparse[i]. If that value happens to be greater than MAXINT, it'll miss your n<0 check and Read AV.

I think it's a reasonable presumption that i will be generated in such a manner that it will fit into sparse[]. But you're making a post about how you can handle arbitrary values in memory -- you fail on half the values right now :)

@mobius: Yes. But a set is a data structure that ...

2008-03-16T12:39:00.000-04:00

@mobius: Yes. But a set is a data structure that only stores each element once, so that's okay. Or if you adapt it to do what the exercises asked, dense contains the list of vector indices that have been initialized with data. Either way, it's not a real restriction that the elements of dense be unique.

Don't the elements of dense[] have to be unique in...

2008-03-16T12:27:00.000-04:00

Don't the elements of dense[] have to be unique integers for this to work? I

Very cool. I will use this some day.

2008-03-16T10:30:00.000-04:00

Very cool. I will use this some day.

@dan: Yes: i is unsigned, and in general add-membe...

2008-03-16T08:04:00.000-04:00

@dan: Yes: i is unsigned, and in general add-member needs to check whether the number is already there and all the routines should check i against the size of sparse.

I was trying to keep the presentation simple. The paper has all the gory details.

Hey Russ,Came across this blog through a random li...

2008-03-16T01:44:00.000-04:00

Hey Russ,
Came across this blog through a random link. Then I was like... hey, I know this guy!

Great blog. I've bookmarked it. Hope you're doing well.

AJ

10 print "my brain hurts"20 goto 10

2008-03-16T01:33:00.000-04:00

10 print "my brain hurts"
20 goto 10

drew, Check that n>0 :)

2008-03-16T01:29:00.000-04:00

drew,

Check that n>0 :)

Besides crashing, in the case where sparse[i] is l...

2008-03-16T01:28:00.000-04:00

Besides crashing, in the case where sparse[i] is less than 0, then dense[sparse[i]] is also uninitialized memory. So, if dense[sparse[i]] happens to contain i, then you'll get a false positive for set membership.

(And, of course, I assume that i is constrained to be less than the size of the region malloc'd to sparse)

Took a look at this from a security perspective, s...

2008-03-16T00:30:00.000-04:00

Took a look at this from a security perspective, since at first glance, I thought I was looking at another instance of someone thinking uninitialized RAM contains random data. Actually, this works, and is pretty cool! Here's how it looks, from another lens. The canonical, trusted "array" is the dense array. However, this is potentially slow to access. So, a second array is created, in which the value in the array is itself used as an index into the dense array. Now, the uninitialized memory could contain anything, but the value there will either refer back to the entry in the trusted dataset, or it will not.

One possible source of trouble is the fact that if the same i is added to the array twice, the second entry will blow away the first one in the sparse set, meaning you'll have a value in the dense set with no index entry pointing back to it. For certain scenarios, this could be a problem.

A much bigger issue, however, is that the integer isn't called out as needing to be unsigned :) If it isn't, the memory at sparse[i] could contain a number greater than MAXINT, which would be less than 0, and thus pass n<0 membership. Your system would (likely) crash.

@gruseom: The space cost is 2 words per potential ...

2008-03-15T14:06:00.000-04:00

@gruseom: The space cost is 2 words per potential entry (per universe member). I've changed the wording to be clearer, I hope. The contrast there is just supposed to be the 2 words vs 1 bit.

Very cool. But is it correct to say that the space...

2008-03-15T03:17:00.000-04:00

Very cool. But is it correct to say that the space requirement is two words per element (by which I assume you mean 2*n)? What if one of the integers in the set is very large, wouldn't the sparse vector have to consume correspondingly large space?

There's also constant time remove (though a little...

2008-03-14T18:46:00.000-04:00

There's also constant time remove (though a little more work):

remove-member(i):
if not is-member(i): return
j = dense[n-1];
dense[sparse[i]] = j;
sparse[j] = sparse[i];
n = n - 1

@valhallasw: Thanks for pointing that out. Added ...

2008-03-14T18:43:00.000-04:00

@valhallasw: Thanks for pointing that out. Added some CSS magic to make the pre-blocks wrap.

Doh. The pre-block cuts of anything that comes too...

2008-03-14T18:13:00.000-04:00

Doh. The pre-block cuts of anything that comes too far to the right, so the ==i didn't show up. Never knew pre-blocks within a div could be this evil :)

@valhallasw: It already saiddense[sparse[i]] = i;...

2008-03-14T16:50:00.000-04:00

@valhallasw: It already said
dense[sparse[i]] = i; I've changed = to == so the pseudo-code is more like C.

is-member(i): return sparse[i] < n && dense[spa...

2008-03-14T15:58:00.000-04:00

is-member(i):
return sparse[i] < n && dense[sparse[i]]

Shouldn't this be
return sparse[i] < n && dense[sparse[i]]==i
, as dense can contain null elements. Obviously this only fails with a false=0 representation.