pete@sinix.UUCP (Pete Delany) (08/23/90)
Would someone forward this to Dennis Ritchie, unfortunately I havn't his e-mail address. I just made a 100DM bet that the code found in heap_kmem.c check_need_to_free() is correct where it copies a structure pointed to by a structure onto the first structure with structure assignment: { struct need_to_free { struct need_to_free *addr; int nbytes; } *ntf = &kmem_info.need_to_free_list; *ntf = *(struct need_to_free *) ntf->addr; } +-------------+ +------------+ +-------------+ | | | | | | ntf -> | addr p1 ----------> | addr p2 -------> | addr p3 | | | | | | | +-------------+ +------------+ +-------------+ | | | | | | | nbytes n1 | | nbytes n2 | | nbytes n3 | | | | | | | +-------------+ +------------+ +-------------+ So after the structure should the data structure look like my humble view: ============== +-------------+ +------------+ +-------------+ | | | | | | ntf -> | addr p2 ----------> | addr p3 -------> | addr p4 | | | | | | | +-------------+ +------------+ +-------------+ | | | | | | | nbytes n2 | | nbytes n3 | | nbytes n4 | | | | | | | +-------------+ +------------+ +-------------+ or like my friend thinks "undeterministic", and is this case generating code that leaves the structures looking like: +-------------+ +------------+ +-------------+ | | | | | | ntf -> | addr p2 ----------> | addr p3 -------> | addr p4 | | | | | | | +-------------+ +------------+ +-------------+ | | | | | | | nbytes n3 | | nbytes n4 | | nbytes n5 | | | | | | | +-------------+ +------------+ +-------------+ is just a "feature". Ckecking out the ANSII Oct 31 '88 spec says: "If the value being stored in an object is accessed from another object that overlaps in any way the storage of the first object, then the overlap shall be exact and the two objects shall have qualified or unqualified versions of a compatible type; otherwise the behavior is undefined" Now to better understand this let us assume: ============================================ 1. a structure and an object are the same thing, object is just a OSI'ish term, 2. "in any way" add nothing to the logic of the statement, 3. "ANYTHING or unANYTHING" add nothing to the meaning, 4. overlap storage means overlaping in memory, not symboliclly in the intermediate language of the compiler or it's authors, Then we get the following slightly more understandable statement: ================================================================= "If the data being stored in a structure is accessed from another structure that overlaps the memory storage of the first structure, then the overlap shall be exact and the two structures shall have versions of a compatible type; otherwise the behavior is undefined" Now, breaking it into it's structural components, we get: ========================================================= "If the data being stored in a structure is accessed from another structure : TRUE and that data overlaps the memory storage of the first structure : TRUE, then the overlap shall be exact: TRUE and the two structures shall have versions of a compatible type; :TRUE otherwise "the behavior is undefined" This this reduces to: if(TRUE && TRUE) TRUE; /* OK */ So my interpretation is the behavior is OK. How about it Dennis? I talked to you about 15 years ago when I was upgrading our V6 Honewell Compiler to V7 to do structure assignment and think it would have done it as I see reasonable now. System V, BSD4.3, Sun, and Vax compiler seem to have avoided this bug, so I assume most people expect the structure to be assigned as if done with bcopy(). I don't see the fix being as easy as on Steve Bunches, Dennis's or Johnsons compilers but I do feel it is a bug and not a "feature". What do you guys think? How many people know of existing code that uses this kind of assumpion? Is there much code out there. This kmem_alloc() bug has been irritating me for almost a year SUMMARY: Want opinions from C compiler guru's about what "C" should do. I currently think Dennis is the best authority on C. How about our C++ gurus at the Labs; what should C++ do? And last, but not least, how about our ANSII C committee types, am I interpreting your gospel as it was intended by the almighty? If not a lexical breakdown might be insighfull. DISCLAIMER: Of course my opinion is not likely the same as Siemens, Nixdorf, OSI, ANSII, XOPEN, OSF, or any of the world authorities. However opinions from all are appreciated, especially those helping me win my 100 DM. :-)
cc100aa@prism.gatech.EDU (Ray Spalding) (08/24/90)
In article <1518@athen.sinix.UUCP> pete@sinix.UUCP (Pete Delany) writes: > I just made a 100DM bet that the code found in heap_kmem.c > check_need_to_free() is correct where it copies a structure pointed to by > a structure onto the first structure with structure assignment: > { > struct need_to_free { > struct need_to_free *addr; > int nbytes; > } *ntf = &kmem_info.need_to_free_list; > > *ntf = *(struct need_to_free *) ntf->addr; > } > [...] > Ckecking out the ANSII Oct 31 '88 spec says: > > "If the value being stored in an object is accessed from another > object that overlaps in any way the storage of the first object, > then the overlap shall be exact and the two objects shall have > qualified or unqualified versions of a compatible type; > otherwise the behavior is undefined" It seems to me that the code is just fine, except: (1) As was pointed out in another thread today, there's no guarantee that "kmem_info.need_to_free_list" is represented the same as "struct need_to_free" unless it is defined AS a "struct need_to_free". That is, distinct structs defined with similar source code may not in fact have the same layout in memory. But, one can probably get away with it in this case most times. (2) The cast (struct need_to_free *) seems redundant-- isn't that the declared type of ntf->addr? Couldn't that line just read "*ntf = *ntf->addr;"? Your reference to the standard seems irrelevant here. The value being stored does not overlap the object being stored into at all-- the two objects are in two different, non-overlapping areas of memory (unless the pointers have been corrupted). What the code is doing is just using the value of an object in computing it's own new value, not unlike "i = i + 1". (We'd write that differently, of course). -- Ray Spalding, Technical Services, Office of Information Technology Georgia Institute of Technology, Atlanta Georgia, 30332-0275 uucp: ...!{allegra,amd,hplabs,ut-ngp}!gatech!prism!cc100aa Internet: cc100aa@prism.gatech.edu
pete@sinix.UUCP (Pete Delany) (09/05/90)
In article <12939@hydra.gatech.EDU> cc100aa@prism.gatech.EDU (Ray Spalding) writes: >It seems to me that the code is just fine, except: >(1) As was pointed out in another thread today, there's no guarantee >that "kmem_info.need_to_free_list" is represented the same as "struct >need_to_free" unless it is defined AS a "struct need_to_free". Great thats one vote for the compiler having a BUG, thanks. But we need lots more votes; keep thoses votes comming in. Your right kmem_info.need_to_free_list should have been declared in the example, it is in ../sys/heap_kmem.c. >That is, distinct structs defined with similar source code may not in fact >have the same layout in memory. But, one can probably get away with it >in this case most times. What? I thought all structures for the save archecture have the same layout. At least for the same system. Right? >(2) The cast (struct need_to_free *) seems redundant-- isn't that the >declared type of ntf->addr? Couldn't that line just read >"*ntf = *ntf->addr;"? Your right, in trying to simplify the example I missed that. I should have made it: struct need_to_free { struct need_to_free *addr; int nbytes; }; struct kmem_info { int misc_stuff; struct neet_to_free need_to_free_list; } check_need_to_free() { struct need_to_free *ntf = &kmem_info.need_to_free_list; again: ntf = &kmem_info.need_to_free_list; if(ntf->addr) { int addr = *ntf->addr; int nbytes = *ntf->addr; *ntf = *ntf->addr; /* BUG or FEATURE */ kmem_free(addr, nbytes); goto again; } } ======== Unfortuneately I currently have to hack the kernel with something like: ======== #define COMPILER_STRUCTURE_ASSIGNMENT_BUG struct need_to_free { struct need_to_free *addr; int nbytes; }; struct kmem_info { int misc_stuff; struct neet_to_free need_to_free_list; } check_need_to_free() { struct need_to_free *ntf = &kmem_info.need_to_free_list; again: ntf = &kmem_info.need_to_free_list; if(ntf->addr) { int addr = *ntf->addr; int nbytes = *ntf->addr; #ifdef COMPILER_STRUCTURE_ASSIGNMENT_BUG tmp_ntf = *ntf->addr; *ntf = tmp_ntf; #else *ntf = *ntf->addr; /* BUG or FEATURE */ #endif kmem_free(addr, nbytes); goto again; } } ======== I wonder why no one else has an opinion on the efficiecy of this code. Clearly we think the the structure pointed to by ntf->addr will be copied to kmem_info.need_to_free_list. Unfortunately it's not clear yet that all us non-authoritians see it that way, or, that the great wizzards and central committee types give it their blessing. > >Your reference to the standard seems irrelevant here. The value being >stored does not overlap the object being stored into at all-- the two >objects are in two different, non-overlapping areas of memory (unless >the pointers have been corrupted). Perhaps the greatest reason that I presented the ANSI C paragraph is that my friend, who accepted my DM100 bet, presented it to me as the defense to his position; insisting that the structures did overlap. So I have tried to see the efficiacy of his position. But as you can see from my posting, that upon rearranging the text from committee language to english to simple logic that it doesn't seem to defend his position. Clearly Ray agrees with me and the authors of the heap_kmem.c code. Unfortunately, just your opinion likely wont get our corporative digestive track accepting this 'feature' as a BUG without either *lots* of opinions (come on guys how about a tiny posting) or words-of-wisdom from the authorities or powers that be. I also expect that a single 'yea' is not sufficient to win my DM 100 so I can buy some cheap silver; Hmmm I wonder if Rosenthal is right about sivler going to $4 and then to $10 or higher. Lets see DM100 => about a pound of sterling silver dollars; ... Where are Dennis Ritchie and the ANSI C party types when you need them? :-) -pete
danm@hpnmdla.HP.COM (Dan Merget) (09/10/90)
> { > struct need_to_free { > struct need_to_free *addr; > int nbytes; > } *ntf = &kmem_info.need_to_free_list; > > *ntf = *(struct need_to_free *) ntf->addr; > } I don't claim to be any C guru (I'm still trying to decipher that ANSI paragraph you quoted). However, it seems to me that your code simply copies the first sizeof(struct need_to_free) bytes from the second object in the linked list to the first object. In that case, I think that your code would give you the following linked list: +-------------+ +------------+ +-------------+ | | | | | | ntf -> | addr p2 ----------> | addr p3 -------> | addr p4 | | | | | | | +-------------+ +------------+ +-------------+ | | | | | | | nbytes n1 | | nbytes n3 | | nbytes n4 | | | | | | | +-------------+ +------------+ +-------------+ To get the result you're looking for, the last line of code should be either: ntf = ntf->addr; or: *(need_to_free_list_type *) ntf = *(need_to_free_list_type *) ntf->addr; where "need_to_free_list_type" is the type of kmem_info.need_to_free_list. On the other hand, maybe I simply need to sign up for "Oversimplifiers Anonymous". :-) _ | | /\ ________________________________________________ __| |__/ /_/\____/\__\ This note is not intended to represent the \ / _ |_ __/ \__/ \___ viewpoints of my god, my country, my company,\ / / | |/ / / /\ \/ /\ \ \ or my family. I'm not even certain that \ \ \_| |\ \/\ \ \ / / / / it accurately represents my own. / \____| \__/\/ \/ \/ /_______________________________________________/ Dan Merget danm@hpnmdla.HP.COM