This is pcn_tags.h in view mode; [Download] [Up]
/* * PCN System * Author: Steve Tuecke * Argonne National Laboratory * * Please see the DISCLAIMER file in the top level directory of the * distribution regarding the provisions under which this software * is distributed. * * pcn_tags.h * * The tag values used by the assembler, linker, and runtime system. * * A discussion of the tags can be found in a comment near the end * of this file. */ #ifndef _PCN_INCLUDE_PCN_TAGS_H #define _PCN_INCLUDE_PCN_TAGS_H /* * Number of bits for the tag */ #define TAG_SIZE 5 /* * All tags (except REF_TAG) must have a low order bit of 1. */ #define REF_TAG 0 #define UNDEF_TAG 1 #define RREF_TAG 3 #define TUPLE_TAG 5 #define INT_TAG 7 #define STRING_TAG 9 #define DOUBLE_TAG 11 #define TRAILER_TAG 13 #define UNDEF_TRAILER_TAG 15 #define RREF_TRAILER_TAG 17 #define PROC_RECORD_TAG 19 #define VALUE_NOTE_TAG 21 #ifdef STREAMS #define STREAM_TAG 23 #endif /* * The following are the remaining available tags: * 25 27 29 31 */ #define PCN_TAG_NAMES \ { \ "REF_TAG", \ "UNDEF_TAG", \ "REF_TAG", \ "RREF_TAG", \ "REF_TAG", \ "TUPLE_TAG", \ "REF_TAG", \ "INT_TAG", \ "REF_TAG", \ "STRING_TAG", \ "REF_TAG", \ "DOUBLE_TAG", \ "REF_TAG", \ "TRAILER_TAG", \ "REF_TAG", \ "PROC_RECORD_TAG", \ "REF_TAG", \ "VALUE_NOTE_TAG", \ "REF_TAG", \ "STREAM_TAG", \ "REF_TAG", \ "UNUSED_TAG", \ "REF_TAG", \ "UNUSED_TAG", \ "REF_TAG", \ "UNUSED_TAG", \ "REF_TAG", \ "UNUSED_TAG", \ "REF_TAG", \ "UNUSED_TAG", \ "REF_TAG", \ "UNUSED_TAG" \ } #ifndef PCN #ifdef DEFINE_PCN_TAG_NAMES #ifdef GLOBAL #define PCN_TAGS_GLOBAL GLOBAL #ifdef DEFINE_GLOBALS #define PCN_TAGS_DEFINE_GLOBALS DEFINE_GLOBALS #endif #else #define PCN_TAGS_GLOBAL #define PCN_TAGS_DEFINE_GLOBALS #endif PCN_TAGS_GLOBAL char *_p_tag_name[] #ifdef PCN_TAGS_DEFINE_GLOBALS = PCN_TAG_NAMES #endif ; #endif /* DEFINE_PCN_TAG_NAMES */ #endif /* !PCN */ /****************************************************************** Discussion of tags (or "Why tags are the way they are") ======================================================= To support the Morris garbage collection algorithm in PCN, all pointers (conceptually, at least) need to have two extra flags during the garbage collection: marked : This pointer is in use, so it needs to be gc's reversed: This pointer has been reversed. However, there is no need to actually support a 'marked' bit in each pointer, because the location of a pointer on the heap implies if its marked or not. That is, the only pointers that we will encounter on the heap that will point to other structures on the heap will be in tuples, and if the tuple is marked then this implies that the pointer in the tuple is marked. Thus, there is no need for a 'marked bit in each pointer, but only in the header cell of data structures. In addition, during the emulator run, pointers must be distinguishable from tags. This is accomplished by exploiting the fact that pointers are word aligned, so the low two bits are 0. But during the gc, since we need an extra bit for the 'reversed' flag, we'll grab the second bit. Therefore, during the gc, pointers are distinguished by the fact that the low bit is 0. The second lowest bit is 0 if it is not reversed, or 1 if it is reversed. Therefore, tags must have a low order bit of 1. Assuming four additional tag bits, this yields 16 legal tags. (i.e., The odd integers between 1 and 31, inclusive.) In addition, assume that the pointer dereferencing routine stops when it hits a cell where the two low order bits are not both zero. This has the nice effect that a reversed pointer will stop a pointer dereference. This property is exploited in the combined mark stage + offheap pointer reversal stage, as described below. Double word alignment --------------------- Most of the new microprocessors require double word alignment of double precision floats (at least to achieve maximum efficiency). In the old implementation (stop and copy garbage collector), this was handled by just skipping a cell on the heap if need be before allocating room for the double. However, this method will not work with the Morris algorithm, because it needs to know the exact amount of garbage before collection begins. So we cannot just add spaces whereever we feel like. Therefore, if double word alignment is required, all data structures must consume an even number of words, and must be double word aligned on odd words (i.e., the data header cell is double word aligned on an odd word so that the actual data contained in the data structure is double word aligned on the even word). In some cases (tuples, integers, characters) this means padding the size out. Trailer tag cell ---------------- Since the Morris garbage collection algorithm must be able to distinguish data structures when linearly scanning the heap from either direction, all data structures that are more than one cell in size must have some sort of tag cell at each end of all data structures. However, this trailing tag is not used for anything other than the reverse scan in the gc. Therefore, it need not carry complete information (i.e., tag, size, etc). Instead, a special tag (TRAILER_TAG) is used at the end of all multi-cell data structures on the heap, with the exception of of undefs and rref, which have their own special trailer cell. The non-tag bits of the trailer cell contain the offset (in cells) from that trailer cell to the data header tag cell. Thus, the header tag cell of the data structure can be found by simply subtracting the trailer cell size field from the trailer cell location. This results in data structures having the following sizes (in cells, assuming 32-bit cells with double word alignment of doubles): undef - 2 (tag + undef_trailer) rref - 6 (tag + weight + irt_location + node + pad + rref_trailer) tuple - 2 + arity + possible_pad int - 2 + size + possible_pad string - 2 + size_in_cells + possible_pad double - 2 + 2*size On 64-bit machines, there is no need for inserting pad word, since all cells are already double word aligned. Likewise, on machines that do not require double word alignment of doubles, there is no need for inserting pad words, since we do not need to make all data structures have an even number of words. Data header cell layout + resulting size limitations ---------------------------------------------------- Given these constraints, a data header cell has the following layout: bits 0 - 4 : tag, where the low bit is 0 if its a pointer (reference), or 1 if its a data structure tag bit 5 : mark, for garbage collection, and for temporary use by PDB bits 6 - ?? : size Assuming a 32 bit machine: 1) This leaves 26 bits for the 'size' field. Since the 'size' field of a trailer cell contains the offset in cells to the header cell, the maximum size in cells of any data structure is 2^26-2 (67108862 or about 67 million cells). Similarly, the 'size' field of a header cell contains the number of elements in that data structure. These two constraints translate to maximum array sizes of: Double: (2^26-2)/2 = 33554431 elements (~33.5 million) Tuple or Integer: 2^26-2 = 67108862 elements (~67 million) Character: 2^26-2 = 67108862 elements (~67 million) 2) Undefs and rrefs use the header and trailer cells somewhat differently than the other data structures. Since undefs and rrefs both have a constant size, the 'size' field of the header and trailer cells can be used for other purposes. In particular, these extraneous 'size' fields are used to hold information about the suspension queue that is hung off of this undef or rref. Since process records are alloced off the heap using malloc, undefs and rrefs need full 32 bit pointers to point to a suspension queue. However, we do not want to add an additional full word to each of these data structures just to hold this pointer. (Note: On a double word aligned machine, this would require undefs to be 4 words -- header, pointer, pad, trailer.) Instead, we break the pointer up into two parts (its high and low order bits) and put those parts in the 'size' fields of the header and trailer cells, respectively. Therefore, there is no limitation on the location or number of process records. ******************************************************************/ #endif /* _PCN_INCLUDE_PCN_TAGS_H */
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.