C Arch patterns

There are some patterns you can see in C code.
Mostly signs that give off indications of what are the data structures used.

For example, this is a code from cpython source(Include/object.h):(obfuscated for illustrative purposes)

typedef struct XXX {
struct XXX *nnn;
const char* string;
PyObject *object;
} XXX;

The sign here is that the struct name (XXX here) is used, within the
struct definition for another element. In this case, this element is a pointer to the self. This indicates this is a linked list.

It can be a circular linked list or singly linked list with the last node pointing to NULL. That distinction can be guessed with initial values. Given it’s not being initialized, I would guess this is a circular linked list, but to verify I will have to check parts of the code where this struct is initialized.

On the contrary, if I had needed this to be a doubly linked list instead, I would have defined it this way instead.

typedef struct XXX {
struct XXX *ppp;
struct XXX *nnn;
const char* string;
} XXX;

The point being two pointers to the same structure, but this does not necessarily mean there’s a doubly linked list implementation. If someone’s trying to write Obfuscated C code, they might use this struct but use it differently, on purpose to hinder code readability.

Oh, by the way, this could also be made into a binary-tree structure by manipulating the insertions into *ppp, *nnn, as new structs. In case of making this a binary tree, we would need a check to make sure no new object linked to *nnn(and *ppp) is already in the structure. Infact it would be more apt naming those *left and *right than *ppp, *nnn.

i.e:

typedef struct XXX {
struct XXX *left;
struct XXX *right;
const char* nodelabel;
} XXX;

Note purely in terms of the type of elements composing/constituting the struct, there’s no difference between this and the above doubly linked list. However, the difference will arise out of how these struct pointers are inserted.
#TODO: CODE SAMPLE HERE.

Now, I’ll graduate to the next data structure, I believe is logically next, (and is one of my favourite) data structure — Graphs.

Linked lists, are simply a very specific case of a graph(which can be called a specific case of sets).
Linked lists are simply graphs restricted to only one edge,(directed) between any two nodes.
Ofcourse, am assuming planar graph<link>,(i.e: one edge can only connect two nodes) and not hyper-graph<link>(think nodes in 3D, and edges that can connect more than “2 nodes”.)

So, Opencog<link> is a open-source attempt to create an Artificial General Intelligence system.
At the core of it is a hypergraph<link to why hypergraphs>(aka atomspace).
Note: this is a C++ project.

Here’s the code for defining an atom:

class Atom
: public std::enable_shared_from_this<Atom>
{
friend class ::AtomUTest; // Needs to call setFlag()
friend class AtomTable; // Needs to call MarkedForRemoval()
friend class ImportanceIndex; // Needs to call setFlag()
friend class Handle; // Needs to view _uuid
friend class SavingLoading; // Needs to set _uuid
friend class TLB; // Needs to view _uuid

private:
//! Sets the AtomTable in which this Atom is inserted.
void setAtomTable(AtomTable *);

//! Returns the AtomTable in which this Atom is inserted.
AtomTable *getAtomTable() const { return _atomTable; }

protected:
UUID _uuid;
AtomTable *_atomTable;

Type _type;
char _flags;

TruthValuePtr _truthValue;
AttentionValuePtr _attentionValue;

// Lock needed to serialize AV changes.
// Just right now, we will use a single shared mutex for all
// locking. If this causes too much contention, then we can
// fall back to a non-global lock, at the cost of 40 additional
// bytes per atom.
static std::mutex _avmtx;
static std::mutex _mtx;

/**
* Constructor for this class.
*
* @param The type of the atom.
* @param Outgoing set of the atom, that is, the set of atoms this
* atom references. It must be an empty vector if the atom is a node.
* @param The truthValue of the atom. note: This is not cloned as
* in setTruthValue.
*/
Atom(Type, TruthValuePtr = TruthValue::NULL_TV(),
AttentionValuePtr = AttentionValue::DEFAULT_AV());

struct InSet
{
// incoming set is not tracked by garbage collector,
// to avoid cyclic references.
// std::set<ptr> uses 48 bytes (per atom).
IncomingSet _iset;
// Some people want to know if the incoming set has changed...
AtomPairSignal _addAtomSignal;
AtomPairSignal _removeAtomSignal;
};
typedef std::shared_ptr<InSet> InSetPtr;
InSetPtr _incoming_set;
void keep_incoming_set();
void drop_incoming_set();

// Insert and remove links from the incoming set.
void insert_atom(LinkPtr);
void remove_atom(LinkPtr);

private:
/** Returns whether this atom is marked for removal.
*
* @return Whether this atom is marked for removal.
*/
bool isMarkedForRemoval() const;

/** Returns an atom flag.
* A byte represents all flags. Each bit is one of them.
*
* @param An int indicating which of the flags will be returned.
* @return A boolean indicating if that flag is set or not.
*/
bool getFlag(int) const;

/** Changes the value of the given flag.
*
* @param An int indicating which of the flags will be set.
* @param A boolean indicating the new value of the flag.
*/
void setFlag(int, bool);

//! Marks the atom for removal.
void markForRemoval();

//! Unsets removal flag.
void unsetRemovalFlag();

public:

virtual ~Atom();

/** Returns the type of the atom.
*
* @return The type of the atom.
*/
inline Type getType() const { return _type; }

/** Returns the handle of the atom.
*
* @return The handle of the atom.
*/
inline Handle getHandle() {
return Handle(shared_from_this());
}

/** Returns the AttentionValue object of the atom.
*
* @return The const reference to the AttentionValue object
* of the atom.
*/
AttentionValuePtr getAttentionValue() const { return _attentionValue; }

//! Sets the AttentionValue object of the atom.
void setAttentionValue(AttentionValuePtr) throw (RuntimeException);

/** Returns the TruthValue object of the atom.
*
* @return The const referent to the TruthValue object of the atom.
*/
TruthValuePtr getTruthValue() const { return _truthValue; }

//! Sets the TruthValue object of the atom.
void setTruthValue(TruthValuePtr);
void setTruthValue(CompositeTruthValuePtr ctv) {
setTruthValue(std::static_pointer_cast<TruthValue>(ctv));
}

//! Return the incoming set of this atom.
IncomingSet getIncomingSet() const;

/** Returns a string representation of the node.
*
* @return A string representation of the node.
*/
virtual std::string toString(std::string indent = "") const = 0;
virtual std::string toShortString(std::string indent = "") const = 0;

/** Returns whether two atoms are equal.
*
* @return true if the atoms are equal, false otherwise.
*/
virtual bool operator==(const Atom&) const = 0;

/** Returns whether two atoms are different.
*
* @return true if the atoms are different, false otherwise.
*/
virtual bool operator!=(const Atom&) const = 0;
};

Whoa, C++, reputation of being verbose and fearsome is justified, i think. Now let’s break this down.
# TODO: EXPLAIN THE STRUCT
Let’s now check one of my favourite project redis, And a data structure/algorithm that fascinates me. The hyperloglog, HLL


struct hllhdr {
char magic[4]; /* "HYLL" */
uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */
uint8_t notused[3]; /* Reserved for future use, must be zero. */
uint8_t card[8]; /* Cached cardinality, little endian. */
uint8_t registers[]; /* Data bytes. */
};

Now this looks simple, and some of you might think it’s deceptively simple.(Don’t it’s straight forward simple). The real magic is actually in how these values are computed. There’s a reason HLL is called an algorithm and not considered a data structure.
#TODO: MORE ELABORATION

Deep C++ —- virtual table

Moving further along in that ridiculously long, too many slides unneccessarily pdf Deep C, we come across Deep C++ .


#include

struct X
{
int a;
char b;
int c;

};

int main(void)
{
std:: cout << sizeof(X) << std::endl;
return 1;

}

Now that code is no different from C by much(Except for those std::cout instead of printf) and so should print out the same size as padded structs in C. (see prev post)
So it does:

 g++ cpp_vtable.cpp  -o cpp_vtable
anand@anand-usb-boot:C [master] $ gdb64 cpp_vtable
Reading symbols from /home/anand/workspace/github_stuff_public/Miscellaneous/C/cpp_vtable...(no debugging symbols found)...done.

(gdb) run
Starting program: /home/anand/workspace/github_stuff_public/Miscellaneous/C/cpp_vtable 
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x7ffff7ffa000
12

Now what happens if we add a member function to that struct? Let’s see:
Am adding this line to the end of the struct.

void set_value(int v) {a = v; }

Well it still prints the same 12. What does this mean? According to the pdf, normal member functions to C++ are just syntactic sugar and are equivalent to C functions with having an additional argument in the first position as being the struct which they are a member of.

That’s why we get this output:

 g++ cpp_vtable.cpp  -o cpp_vtable
anand@anand-usb-boot:C [master] $ gdb64 cpp_vtable
Reading symbols from /home/anand/workspace/github_stuff_public/Miscellaneous/C/cpp_vtable...(no debugging symbols found)...done.
(gdb) run
Starting program: /home/anand/workspace/github_stuff_public/Miscellaneous/C/cpp_vtable 
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x7ffff7ffa000
12

OK that no loadable sections found warning from gdb is weird.. but otherwise the output is the same 12 as expected.

Now let’s go ahead and make it a virtual function instead.


virtual void set_value(int v) {a = v; }

And here’s the result of compiling and running it


anand@anand-usb-boot:C [master] $ g++ cpp_vtable.cpp  -o cpp_vtable
anand@anand-usb-boot:C [master] $ gdb64 cpp_vtable

(gdb) run
Starting program: /home/anand/workspace/github_stuff_public/Miscellaneous/C/cpp_vtable 
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x7ffff7ffa000
24
[Inferior 1 (process 8290) exited with code 01]
(gdb) run
Starting program: /home/anand/workspace/github_stuff_public/Miscellaneous/C/cpp_vtable 
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x7ffff7ffa000

Breakpoint 1, 0x0000000000400830 in main ()

Hmm we still get the same warning, but the size has been doubled. It must be the virtual table pointer. But how do we know, it’s not allocating memory separately for a virtual functions. Time to add another func to the source code.

So here’s how the new struct looks like:

struct X
{
int a;
char b;
int c;
virtual void set_value(int v) {a = v; }
virtual int get_value(int v) {return a; }
virtual void increase_value() { a++;}

};

And here’s the output of running the program.

anand@anand-usb-boot:C [master] $ g++ cpp_vtable.cpp  -o cpp_vtable
anand@anand-usb-boot:C [master] $ gdb64 cpp_vtable
GNU gdb (GDB) 7.5.91.20130417-cvs-ubuntu

(gdb) run
Starting program: /home/anand/workspace/github_stuff_public/Miscellaneous/C/cpp_vtable 
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x7ffff7ffa000
24
[Inferior 1 (process 8353) exited with code 01]
(gdb) 

You can see that the size is the same as previous code 24. So it confirms if there’s a virtual function, there’s a pointer to a virtual table created as part of the structure. Infact, this same virtual table is used for verifying that inheriting classes, ensure overriding the virtual functions.

By inductive reasoning the next step is to simply add another struct to the code and see what happens.

Here’s what happens, if i copy paste the same struct as struct Y and keep only the get_value virtual function.

anand@anand-usb-boot:C [master] $ g++ cpp_vtable.cpp  -o cpp_vtable
anand@anand-usb-boot:C [master] $ gdb64 cpp_vtable
(gdb) run
Starting program: /home/anand/workspace/github_stuff_public/Miscellaneous/C/cpp_vtable 
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x7ffff7ffa000
24
24
[Inferior 1 (process 8674) exited with code 01]
(gdb) quit

Just as expected it’s the same size, and is printed as we coded. :) . So each struct really does have a separate virtual table. We have nullified the hypothesis that all structs/classes share a virtual table.

Next, test would be to see if inherited classes shared a vtable or not, but i’ll save that for some other time.

Deep C- struct packing

Once again, from Deep C. The size of structs.

The basic idea is to test the knowledge that sometimes compilers do optimizations on how the structure is situated in memory. According to the pdf, this is because most hardware architectures are optimized for byte sized access, and so compilers generally pad structures and their elements so that they can be accessed in a byte wise manner. Now this may have been true sometime back, and perhaps still true in a statistical majority sense, but with the profusion of mobile computing devices, I suspect new architectures might have a more fine-grained(than word) access. Anyway,that’s marked for future research. Besides, given how much we have shrunk memory, that’s probably not the case for Smartphones and tablet. They probably still use word optimized architectures. I suppose the older (voice calls only) phones had architectures where this was false. I also think other microcontroller based devices like RSA Security code generators, active noise cancelling chips on headphones/earphones etc.. (aka, wherever memory is still a constraint) this would make a difference, and their architectures might not have inefficient access for sub-word memory accesses.

For now, I’ll just go on with the code and a demo here.


#include

struct X { int a; char b; int c;};

int main(void)
{
printf("%zun",sizeof(int));
printf("%zun",sizeof(char));
printf("%zun",sizeof(struct X));

}

And here’s the output with the minimal set of compilation flags.

anand@anand-usb-boot:C [master] $ gcc struct_padding.c -o struct_padding
anand@anand-usb-boot:C [master] $ ./struct_padding 
4
1
12

Now am running a 64-bit machine, but with 32-bit mode.(Am just reverse guessing since it printed 12, but doesn’t matter for our purposes.
As expected the struct is padded to 12 bytes. Instead of the sum of it’s parts, which is 4+1+4 = 9.

Now let’s add the -fpack-struct option to the gcc command.

anand@anand-usb-boot:C [master] $ gcc struct_padding.c -o struct_padding -fpack-struct
anand@anand-usb-boot:C [master] $ ./struct_padding 
4
1
9

Voila, there it is. the size as our mental model says it should be.
Let’s go add another char pointer to the struct

#include

struct X { int a; char b; int c; char *d;};

int main(void)
{
printf("%zun",sizeof(int));
printf("%zun",sizeof(char));
printf("%zun",sizeof(char *));
printf("%zun",sizeof(struct X));

}


Here’s the output with

anand@anand-usb-boot:C [master] $ gcc struct_padding.c -o struct_padding
anand@anand-usb-boot:C [master] $ ./struct_padding 
4
1
8
24

Here’s the output with -fpack-struct:

gcc struct_padding.c -o struct_padding -fpack-struct
anand@anand-usb-boot:C [master] $ ./struct_padding 
4
1
8
17

That 17 with pack-struct is expected. Note that the pointer size is 8 and without pack-struct it pads up from 20 to 24.

Another good link I came across is this

Calling conventions, ABIs

Well, In another set of weird “following my nose”* instances, I end reading up about cdecl calling conventions for x86.

Turns out there’s more layers involved in between the conversion of C-code to executable than the ones I was aware of.
Not only that there’s a compiler and linker stage, they are there to provide abstractions about the hardware.

Now, that’s not new, anyone who took a basic peek at Operating Systems course can tell you that.
The interesting part according to this wikipedia page
is that there’s something called an Application Binary Interface.

And then there are calling conventions. These turn out to be a set of standards agreed on by hardware manufacturers.
It turns out they needed such a thing because before microcomputers, each hardware manufacturer used to supply his own OS and compilers.

Anyway, to be specific about the cdecl, the core part or according to the wikipage the core part is,
how the caller function, callee function is translated to assembly.

And as the page says the basic idea is to push some values on to the stack by the caller function, call and once returned, clean up the stack.


caller:
    push    ebp
    mov     ebp, esp
    push    3
    push    2
    push    1
    call    callee
    add     esp, 12
    add     eax, 5
    pop     ebp
    ret

Anyway, this obviously led on to one more click and read on wikipage for ABIs.
Ok, I read this page, but most of the sentences just don’t hit any connections in my brain. No wonder, I don’t have all the context or experience,
involved in working at the System internals levels. So this I won’t bother re-phrasing/summarizing.
Here’s the verbatim of Wiki page:
ABIs cover details such as:

the sizes, layout, and alignment of data types
the calling convention, which controls how functions’ arguments are passed and return values retrieved; for example, whether all parameters are passed on the stack or some are passed in registers, which registers are used for which function parameters, and whether the first function parameter passed on the stack is pushed first or last onto the stack
how an application should make system calls to the operating system and, if the ABI specifies direct system calls rather than procedure calls to system call stubs, the system call numbers
and in the case of a complete operating system ABI, the binary format of object files, program libraries and so on.

A complete ABI, such as the Intel Binary Compatibility Standard (iBCS),[1] allows a program from one operating system supporting that ABI to run without modifications on any other such system, provided that necessary shared libraries are present, and similar prerequisites are fulfilled.

Other ABIs standardize details such as the C++ name mangling,[2] exception propagation,[3] and calling convention between compilers on the same platform, but do not require cross-platform compatibility.

EABI

An embedded-application binary interface (EABI) specifies standard conventions for file formats, data types, register usage, stack frame organization, and function parameter passing of an embedded software program.

The main differences of an EABI with respect to an ABI for general purpose operating systems are that privileged instructions are allowed in application code, dynamic linking is not required (sometimes it is completely disallowed), and a more compact stack frame organization is used to save memory.[4]

* — I think the trail I followed was looking for bugs on cpython bugs page,
while came across one about ctypes module, went fishing after it, mucked around ctypes module and the examples provided there,
Ran into some error(original example was tried on windows + cygwin env), tried to figure out that problem and ended up cdecl,
while reading some blog post about ctypes usage, duh…

Debugging a redis contribution– adding bloom filter

I got stuck on this weird segmentation fault during my attempt to add bloom filter to redis. (See here for source.)

Running redis server with gdb and then printing out variables, i concluded that the Bloom filter struct’s member variable a points to an unassigned or atleast out of bounds memory address.

Now, my first thought was that damn may be it’s because default redis make creates the redis binary with gcc optimizations enabled. So  I did a

<blockquote>

make clean

followed it up with a

make noopt

as suggested by this part in the Makefile here.

noopt:
       $(MAKE) OPTIMIZATION=”-O0″

But that didn’t solve any of my problems. So at first , i blamed the Makefile saying it doesn’t propagate the -O0. But then decided, I’ll try the same scenario on a small test code. After all, there’s a lot that I don’t know about  systems programming. So i created a struct with some char pointers, created two pointers to the struct, initialized one, pointed the second pointer to first (after casting the first one to void*). Basically this is what happens with the redis as I pass the pointer to my bloom filter object to redis createObject function.  You can see here.

BLOOM *b = bloom_create(REDIS_BLOOM_FILTER_SIZE,fp);
redisLog(2,”Created BloomFilterObject n”);
robj *o = createObject(REDIS_BLOOM_FILTER,b);

Now for the test code.

#include 
typedef struct testA
{
    int a;
    float b;
    char *c;
}test;

void main()
{
    test *A,*B;

    A->a = 5;
    A->b= 12.0;
    A->c = "eue";

    //B = malloc(sizeof(test));
    B = (void*) A;

    printf("%dt %f t %s n ",B->a,B->b,B->c);
    //free(B);
}

You can find those here.

Anyway, as i run this and here’s the output