From: CRDGW2::CRDGW2::MRGATE::"SMTP::PREP.AI.MIT.EDU::INFO-G++-REQUEST" 17-JUL-1989 11:10 To: MRGATE::"ARISIA::EVERHART" Subj: gnu c++ mi class layout Received: by life.ai.mit.edu (4.1/AI-4.10) id AA14503; Sun, 16 Jul 89 16:48:55 EDT Return-Path: Received: from tut.cis.ohio-state.edu by life.ai.mit.edu (4.1/AI-4.10) id AA14021; Sun, 16 Jul 89 16:31:51 EDT Received: by tut.cis.ohio-state.edu (5.61/4.890612) id AA21131; Sat, 15 Jul 89 13:36:47 -0400 Received: from USENET by tut.cis.ohio-state.edu with netnews for info-g++@prep.ai.mit.edu (info-g++@prep.ai.mit.edu) (contact usenet@tut.cis.ohio-state.edu if you have questions) Date: 14 Jul 89 23:27:35 GMT From: pacbell!osc!strick@ames.arc.nasa.gov (henry strickland) Organization: the techwood toaster pastry users group Subject: gnu c++ mi class layout Message-Id: <409@osc.COM> References: <18498@mimsy.UUCP>, <2129@randvax.UUCP> Sender: info-g++-request@prep.ai.mit.edu To: info-g++@prep.ai.mit.edu [] CLASS LAYOUT FOR G++ (1.35.1- / sun3-os4-nfp) [] [] Henry Strickland (also ) [] Object Sciences Corporation Menlo Park CA I have attempted to reverse-engineer how G++ (v1.35.1-) allocates storage for classes, including multiple inheritance and virtual base cases. This was done by trying things and looking at the output: so it could be wrong. This is for sun3 with os level 4 and no floating point processor, but I don't see why that would matter any. IF ANYONE KNOWS WHERE THE FOLLOWING IS WRONG, PLEASE LET ME KNOW! Also, if anyone knows if cfront 2.0 does things differently, please let me know. I do not have access to cfront 2.0 yet. I am most hesitant about the algorithm at the end for determining virtual base placement. 1. a simple structure A struct has fields for the variables in order. There may be some gaps (dead fields) to meet alignment constraints. Funny cases exist, e.g. structs with no fields, zero-length arrays, bit fields, and they're probably compiler-dependent. Nonvirtual methods (including inlines) require no storage in an instance. EXAMPLE struct A { char a; /* variables */ int x,y; short b; double z; void print(Stream*); /* methods */ }; memory layout A* --> | 1: a | 1: gap | 4: x | 4: y | 2: b | 0: gap? (not on sun3, but on vax, i think) | 8: z 2. a simple structure with a virtual function table There will be ONE anonymous field ("v_ptr") of type (void*) at the end of the structure IF the struct has one or more virtual functions. The format of this virtual function table dependent on whether multiple inheritance is used or not; anyway, it is not described in this document. EXAMPLE struct B { char a; /* variables */ int x,y; short b; float z; void print(Stream*); /* methods */ virtual void one(); /* virtual methods */ virtual int two(char*); virtual int one(int); virtual char* three(char*, int); }; memory layout B* --> | 1: a | 1: gap | 4: x | 4: y | 2: b | 0: gap? | 8: z | 4: vt$B /* virtual func table ptr */ | | | | | V increasing memory addresses V 3. single or multiple inheritance, non-virtual bases The non-virtual superclasses are allocated, in order of appearance on the class definition line, and then the member variables and possibly the virtual function pointer of the current struct. If the superclasses themselves have superclasses or virtual functions, then the layout method is recursive, with each superclass having a full layout within itself. EXAMPLE struct X { /* ... sizeof X is 20 ... */ }; struct Y { /* ... sizeof X is 12 ... */ }; struct Z { /* ... sizeof X is 36 ... */ }; struct M : X, Y, Z { char a; int x,y; short b; float z; void print(Stream*); virtual void one(); virtual int two(char*); virtual int one(int); virtual char* three(char*, int); }; memory layout M* --> | 20: X /* superclasses first */ | 12: Y | 36: Z | 1: a /* M's variables begins */ | 1: gap | 4: x | 4: y | 2: b | 0: gap? | 8: z | 4: vt$M /* virtual func table ptr */ The case of single inheritance is just the multiple-inheritance case with only one superclass. The supers have their virtual function table pointers if they ordinarily need it. The class M only has its own virtual table pointer if M defines new virtual functions that did NOT exist in any of the supers. If M only reimplements virtual functions declared in supers, then M has no v_ptr of its own. 4. multiple inheritance, with virtual bases A class in which itself or ANY of its supers (or any supers of supers, transitively ) has one or more virtual bases, the struct will have two sizes: A "lean" size, which does not count the storage for the virtual bases, and a "full" size, which does count storage for them. Virtual bases are NOT included inside the "lean" structure the way that normal bases are. Instead, only a pointer to the virtual base is stored inside the "lean" structure. These virtual base pointers come at the end of the normal superclasses and before any variables of the current class. There will be one pointer for each virtual base declared as a virtual super of the CURRENT class. If there are virtual bases that are found in the closure of supers but NOT listed in the current struct as a virtual super, there will be no virtual base pointer for this base at this level. These pointers appear in REVERSE order of their declaration: see the diagram. EXAMPLE struct F { /* ... sizeof X is 40 ... */ }; struct G { /* ... sizeof X is 24 ... */ }; struct X { /* ... sizeof X is 20 ... */ }; struct Y { /* ... sizeof X is 12 ... */ }; struct Z { /* ... sizeof X is 36 ... */ }; struct M : virtual F, virtual G, X, Y, Z { char a; int x,y; short b; float z; void print(Stream*); virtual void one(); virtual int two(char*); virtual int one(int); virtual char* three(char*, int); }; *LEAN* layout M* --> | 20: X /* non-virtual | 12: Y superclasses first | 36: Z if any */ | 1: a /* M's variables begins | 1: gap if any */ | 4: x | 4: y | 2: b | 0: gap? | 8: z | 4: POINTER TO G /* virtual base pointers */ | 4: POINTER TO F /* first last */ | 4: v_ptr /* if any */ When an object is instantiated (with operator new) a "full" structure of the specified class is allocated. The full structure includes the lean structure, above, followed by lean structures of all the virtual bases in the superclass closure. The order of the virtual bases is not trivial. The following algorithm FindVirtualBaseOrder() seems to find it. This may not be right -- it is hard to check all the possibilities, but this explains what I've seen so far, and is a fairly likely implementation. It does have its nutty aspects, though, and makes me nervous that I may have missed something. I would have to delve into the compiler code to be absolutely sure. //////////// BEGIN ALGORITHM static List b; static Class orig; FindVirtualBaseOrder( Class c ) { b = NIL; // collect virtual bases on this list orig = c; // remember the original class TraverseClass( c ); return b; // ... the order of the bases in the List b is the order of the // bases after the lean structure for class c // i.e. the most recent addition to b appears first, and the // very first thing that was added comes at the very // end of the full structure. } TraverseClass(Class x) { // this implements a special kind of post-order traversal, // in which we visit traverse the supers of our current // class, and then record all of our virtual supers. // (it is different from a normal post-order in that we do not // record each super immediately after traversing it, but // rather come back and get them after doing all supers.) // It is also strange that the recording of virtual supers // is one backwards ONLY for the original class, and done // frontwards for virtual supers of any transitively-super class. FOR EACH superclass s OF x in the order of declaration in the class definition of x { TraverseClass( s ) } FOR EACH superclass s OF x IF s == orig THEN // the original class in the REVERSE order of declaration in the class def of x ELSE // all supers in the order of declaration in the class definition of x { IF s is a virtual superclass of x AND s is not already in list b { add s to the FRONT of b } } } //////////// END ALGORITHM EXAMPLE class F {...}; class G {...}; class H {...}; class J {...}; class K {...}; class L {...}; class U {...}; class V {...}; class A : virtual U {...}; class B : virtual V {...}; class X : virtual U, A, virtual K, B, virtual L {...}; class Y : virtual V, virtual F, A, B, virtual J {...}; class Z : virtual G, virtual U, virtual V, X, Y, virtual F, virtual H {...}; Flow of algorithm: FindVirtualBaseOrder Z TraverseClass Z TraverseClass G TraverseClass U TraverseClass V TraverseClass X TraverseClass U TraverseClass A TraverseClass U add U <== U TraverseClass B TraverseClass V add V <== V add K <== K // frontwards add L <== L TraverseClass Y TraverseClass V TraverseClass F TraverseClass A TraverseClass U TraverseClass B TraverseClass V add F <== F // frontwards add J <== J TraverseClass F TraverseClass H add H <== H // backwards!! add G <== G So the order of the virtual bases is G, H, J, F, L, K, V, U. layout of a full class Z: Z* zp = new Z; zp --> | Z::X::A ->U // begin A within X within Z | Z::X::A vars // variables for A | Z::X::A vt$A // virt func table for A | Z::X::B ->V | Z::X::B vars | Z::X::B vt$B | Z::X ->U // i.e. pointer to U vars, below | Z::X vars | Z::X vt$X // end X within Z | Z::Y::A ->U | Z::Y::A vars | Z::Y::A vt$A | Z::Y::B ->V | Z::Y::B vars | Z::Y::B vt$B | Z::Y ->V | Z::Y ->F | Z::Y vars | Z::Y vt$Y // end Y within Z | Z ->H // Z names 5 virtual bases | Z ->F // (notice inverse order) | Z ->V | Z ->U | Z ->G | Z vars | Z vt$Z ///// end of lean Z //// | G vars // begin of virtual bases | G vt$G // run algorithm to | H vars // determine ordering | H vt$H | J vars | J vt$J | F vars | F vt$F | L vars | L vt$L | K vars | K vt$K | V vars | V vt$V | U vars | U vt$U // end of full structure 5. other comments I have not been able to get a virtual base that has a virtual base to compile with "g++ version 1.35.1-". I always get this from the compiler: > Failed assertion prev != NULL_TREE at line 2069 of `cplus-search.c'. > g++: Program cc1plus got fatal signal 6. From my understanding of C++, I see no reason why a virtual base cannot have a virtual base, and I see no reason why the above algorithm wouldn't still hold, but I haven't been able to try it. //////////////////////////////////////////////////////////////////////////// strick@osc.osc.com 415-325-2300 uunet!lll-winken!pacbell!osc!strick ( strick@gatech.edu ) They know their limits 'cause they cross 'em every night. -- DEVO -- strick@osc.osc.com 415-325-2300 uunet!lll-winken!pacbell!osc!strick ( strick@gatech.edu )