Jesper Noehr

So I’ve been wanting to write about this for a while. Finally getting around to it.

We’re going to be talking about how to construct and use a flexible permission scheme with Python, and how you can use it in your Django project.

If you’re already a binary ninja, you can skip this section.

The “trick” we’re going to be using, is what’s called “bitwise operators”, namely &, | and <<.

It’s important you know what these do, so lets do a quick tour. We’ll start with the “left shift” operator (<<).

So you know binary, right? Those 1’s and 0’s? OK, good. Lets say that we have the number 2. That’s 10 in binary. Well, actually it’s not 10, it’s 00000010, since there are 8 bits for one byte. The << operator, also called “left shift”, will *move* the bits to the left. So 00000010 << 1 is 00000100, or in decimal, 4. 00000010 << 2 is 00001000, or decimal 8. There’s also the “right shift” operator, so 8>>1 is 4, but we won’t be using that.

There’s an interesting pattern here. All the numbers we get, starting from 1, are in the power of 2, or 2*(2^x), actually. So 2<<4 is the same as 2*(2^4), which is decimal 32.

Now, lets talk about “binary or” (|). This operator, at first sight, may seem like it’s the same as decimal plus (+), since if say 2 | 4, we get 6. But, if we say 6 | 4, we get 6 again. Strange, eh? Not really. The trick here is that “or” will *set* the bit in the originating number, *if it’s not already set*. If it *is* set, it does nothing. Lets drop down to binary again to demonstrate this.

So, using our example of 2 | 4, 2 is 00000010 and 4 is 00000100. 2 | 4 is basically saying “look at the bits in both, and switch all the ones you find on”. So we end up with 00000110, which is…. 6. But wait! 6 is not in the power of 2. You can’t do 2<<x and end up with 6. Thus, we can conclude that 6 is the *combination* of 2<<0 and 2<<1.

In fact, we can construct very large numbers using only “or” and numbers generated by 2<<x, and we can trace it back to the originating numbers. And your computer knows this. We’ll exploit that fact in just a minute.

Finally, lets talk about “binary and” (&). This operator will look at two numbers, and in its result, only return the bits that are set in *both* numbers. This is the operator we’re going to use to “deconstruct” the numbers you or’d together earlier. For example, if we again have 2, which is 00000010, and 6, which is 00000110, it will return 00000010, since only the 7th bit is set in both. Since 6 is constructed from 2 | 4, it will also return 00000100, since 4 is also part of 6. For anything else, it will return 0.

So in summary, 6 & 2 is 2, 6 & 4 is 4, and 6 & 8 is 0.

Application

Lets try it:

CAN_READ = 1<<2
CAN_WRITE = 1<<3
CAN_ADMIN = 1<<4

READER = CAN_READ
WRITER = READER | CAN_WRITE
ADMIN = WRITER | CAN_ADMIN

bob = ADMIN
alice = READER

print "Is Bob an admin?"

if bob & CAN_ADMIN:
    print "Yes!"
else:
    print "No."

print "is Bob a reader?"

if bob & CAN_READ:
    print "Yes!"
else:
    print "No."

print "Is Alice a writer?"

if alice & CAN_WRITE:
    print "Yes!"
else:
    print "No."

print "Is Alice a reader?"

if alice & CAN_READ:
    print "Yes!"
else:
    print "No."

alice |= ADMIN

print "Can Alice write now?"

if alice & CAN_WRITE:
    print "Yes!"
else:
    print "No."

And the output:

$ python bit.py
Is Bob an admin?
Yes!
is Bob a reader?
Yes!
Is Alice a writer?
No.
Is Alice a reader?
Yes!
Can Alice write now?
Yes!

So we’ve defined a very simple permission scheme here, reading, writing and administrating. We’ve defined 3 “flags”, indicating what you can do, and we’ve defined 3 “roles”, defining what each role has access to.

The way this works, comes from what we discussed above. CAN_READ is 4, CAN_WRITE is 8, and CAN_ADMIN is 16. As we saw, we can piece these together using the “or” operator, to get a new number that has that flag “set.” READER is 4, WRITER is 12 (CAN_READ | CAN_WRITE), and ADMIN is 28 (CAN_READ | CAN_WRITE | CAN_ADMIN, or simply WRITER | CAN_ADMIN to add that flag).

Now, with an unsigned integer, we can go up to (2**16)-1 (65535, does that look familiar?), so we can actually fit quite a few more flags in there. How many? You guessed it–16.

In Python, and most other “newer” languages, you don’t really have to worry about unsigned-ness and 8 bit integers, as the language just adjusts the internal representation when you go above the limit. This means that Python won’t really complain if you give it something like 2<<1 | 2<<100, it will just give you back 2535301200456458802993406410756L, indicating that you’re no longer dealing with integers, you’re now dealing with longs. Most database backends support this too–MySQL and PostgreSQL both gives you BIGINT, which will let you go up to 18446744073709551615 (which is (2<<63)-1, hence it’s a 64 bit integer.)

So now you have 64 flags you can mess around with, and you can define these on a *per row/object level basis in a single column/number*! So theoretically, you could eliminate 64 database columns in favor of one number, and you can even use SQL to SELECT it, as SQL *also* supports bitwise operators.

Oh, right, how can you use this in your Django application? Well, we use it heavily on Bitbucket to define permissions to repositories, issues, whatever.

We have a lot of statements that look like this:

if repo.access_for(request.user) & RP.WRITER:
   # allow the write...

And of course, you can construct various other complex comparisons this way.

I hope this has helped you understand basic bitwise operators, and I urge you to dive in further. There’s cool stuff like “not” (~) and “xor” (^), who may be more powerful than what we’ve already demonstrated.

Read more about Bitwise operators on Wikipedia, and have fun.

I found this little guy yesterday. Me and Katie were driving home from my Greek lesson and we could hear something screaming (we had the windows down.)

I pull over, and we walk towards the sound. This was at 10pm, by the way. Just by a dumpster, we see this tiny kitten, screaming his eyes out. Well, that’s a bad analogy, seeing as he’s just a couple of days old and his eyes aren’t even open yet. In fact, one of them was infected, badly.

We take him home and clean up his eye a bit. He doesn’t like that at all, but it needs to be done. We try to feed him a bit with some milk, but we have no way of getting it into his tiny mouth, and he keeps trying to suck on our fingers. Poor thing.

We drive to the vet, but he’s closed. His cell number is on the door though, so we call it. He tells us to go by the 24-hour pharmacy and pick up a syringe. Strangely, they give it to us for free. Needle and everything. Fun.

We head back home, fill it with milk and try to feed him again. Much better this time. This little guy must’ve gulped down about 25ml of milk, and in between meals he also decided to pee on me. Good sign, I think. We put some blankets in a bucket and put him in Katie’s office downstairs. It’s dark there, and he fell asleep instantly. Poor guy must’ve been terrified and exhausted. God knows how long he’s been in that dumpster.

This morning he was still sound asleep in his blankets, with the eventual “mmmm blankets comfy” moves. We haven’t woken him up yet, but we’ll go to the vet this morning. He seems to be doing a lot better.

So, to the people who put him where we found him, and to anyone ever having dumped a litter of kittens in the trash: You need to be arrested and put in jail. You’re inhuman. Animal cruelty is one of the lowest points you can reach in life. If you have a female cat and you don’t want kittens, a) don’t let her go outside and/or b) have her fixed. You need to be responsible. If you *do* end up with kittens, you’re responsible for them, too. What you did was inexcusable and I hope for your sake, that we never meet.

What’s gonna happen to this little guy? I don’t know. Someone we know might want him. If they don’t, we’ll probably adopt him. We already have a cat, but he’s currently back in The Netherlands, getting his vaccinations sorted out. Maybe the two will get along, we’ll see.

One thing’s for sure: We’ll take care of him and make sure he’s happy for as long as we need to.

Easy way to debug what’s going on with your cache:

from django.core.cache import cache as django_cache

class debug_cache(object):
    ignore = [ 'to_slug', 'repodownloadsize' ] # ignore keys starting with these

    def __getattr__(self, attr):
        def wraps(f):
            def i(*args, **kwargs):
                if not any([ args[0].startswith(ig) for ig in debug_cache.ignore ]):
                    print "CACHE %s: args=%s, kwargs=%s" % (attr, args, kwargs)
                return f(*args, **kwargs)
            return i
        return wraps(getattr(django_cache, attr))

if getattr(settings, 'DEBUG_CACHE', False):
    cache = debug_cache()
else:
    cache = django_cache

Put a setting in your settings.py called DEBUG_CACHE = True, and you’ll see what’s going on.

Right, so I’ve decided not to import my old blog entries, with the danger of some linking from other sites going wrong. Since I wrote my own blog software for the last attempt, and it doesn’t have any kind of export functionality + I don’t have time to write it, I’m just going to leave it at that.What will this blog be about? Well, hopefully it will have news about Bitbucket, DVCS in general, Python, maybe some scaling — stuff like that. I’m going away for Xmas vacation on Monday, and will be away for 2 weeks, so until then I won’t have anything on here.Stay tuned.