ObjectManager: why do we have to ensure that the last bit of an object's address is 0

[Ellesar1]

I'm currently trying to understand WoW's object manager and built some basic object manager based on different posts here on MMOwned.

However, I don't understand why we have to check whether the last bit of an object pointer is set to 1 or 0 and to cancel our loop if it is 1. I've tried and it bugs if we omit the check. But why? What does this 1 represent?

	// Iterate through objects
	Object * current;
	_asm {
		mov eax, objectManagerBase;
		add eax, 0xac; // Credits: jbrauman
		mov eax, [eax];
		mov current, eax;
	}
	while (current && (((unsigned int)current & 1) == 0)) { // Credits: EmilyStrange
		cache.push_back(*current);
		current = (*current).nextObject;
	}
	objectCache = cache;

the (((unsigned int)current & 1) == 0) is what I don't understand.

[Oowafas]

The one bit can be set to represent an invalid pointer because an object will never be created without being 4 byte aligned (both the last and 2nd to last bits will always be 0). I don't actually know why it does it that way, maybe because they can only test 1 byte for an invalid pointer as opposed to a 4 byte operand?

[RiotInferno]

I also don't have a concrete answer, but my theory is that it represents the end of the Object list?

[Jadd]

The one bit can be set to represent an invalid pointer because an object will never be created without being 4 byte aligned (both the last and 2nd to last bits will always be 0).

This.

Have fun (:

[flo8464]

The object manager is a linked list. A linked list ends with a NULL-pointer to the next element.

Normally checking for a NULL-pointer should be enough. As far as I know invalid pointers should never occur (well, except its implementation is incorrect which isn't the case), the CPU makes no mistakes. So I don't really get why it's checked.

[Kryso]

IMO because invalidating pointer to next node by setting one bit is faster than setting 4 bytes to 0?

[flo8464]

I am pretty sure next/previous-element pointers get initialized by NULL.

[bigtimt]

actually if you walk the list backwards it just loops. that's how i used to enumerate objects in wowbasic

[Ellesar1]

what do you understand with "walking backwards"? There is only a next - pointer, not a previous-pointer, as far as I know.

And they have to be initialized to 0 since an invalid pointer can be everything random (also even number!)

[namreeb]

The one bit can be set to represent an invalid pointer because an object will never be created without being 4 byte aligned (both the last and 2nd to last bits will always be 0). I don't actually know why it does it that way, maybe because they can only test 1 byte for an invalid pointer as opposed to a 4 byte operand?

This is the correct answer.

[flo8464]

This is the correct answer.

But how can it happen that something like that fails ?

Object someObject;
ObjectList.getCurrentObject()->nextObject = &someObject;

(I know, bad example but should show what I mean).

Is that check something the compiler adds to the code?

[MaiN]

what do you understand with "walking backwards"? There is only a next - pointer, not a previous-pointer, as far as I know.

And they have to be initialized to 0 since an invalid pointer can be everything random (also even number!)

Hmm, isn't it a double linked list?

[namreeb]

But how can it happen that something like that fails ?

Object someObject;
ObjectList.getCurrentObject()->nextObject = &someObject;

(I know, bad example but should show what I mean).

Is that check something the compiler adds to the code?

What do you mean? Is it failing for you? I'm pretty sure this is how the game does it.

[flo8464]

Yeah, but I still don't get how an invalid address can be assigned to that pointer.
Maybe I think overcomplicated, could you please explain it to me.

[namreeb]

It's fairly simple. Rather than null terminating their linked list they chose to set it to an 'odd' value. Alignment says this value is invalid.

EnumVisibleObjects() from WoW:

signed int __cdecl EnumVisibleObjects(int (__cdecl *pCallback)(WGUID, _DWORD), eWOWOBJECTTYPE filter)
{
  int v2; // eax@1
  int v3; // esi@1
  int v4; // ebx@3
  eWOWOBJECTTYPE v5; // edi@5

  v3 = *(_DWORD *)(*MK_FP(__FS__, 44) + 4 * TlsIndex);
  v2 = *(_DWORD *)(*(_DWORD *)(v3 + 8) + 172);
  if ( !(v2 & 1) && v2 )
    v4 = *(_DWORD *)(*(_DWORD *)(v3 + 8) + 172);
  else
    v4 = 0;
  v5 = filter;
  while ( !(v4 & 1) && v4 )
  {
    if ( !((int (__cdecl *)(_DWORD, _DWORD, eWOWOBJECTTYPE))pCallback)(*(_DWORD *)(v4 + 48), *(_DWORD *)(v4 + 52), v5) )
      return 0;
    v4 = *(_DWORD *)(v4 + *(_DWORD *)(*(_DWORD *)(v3 + 8) + 164) + 4);
  }
  return 1;
}

The line of interest there is the while statement. v4 is their iterator. It's anyone's guess why they did it this way.. but they did. Perhaps they use other bits there for something else? It's unimportant.