Archive for January, 2011

Inboxes

When I started using networked computers, I had two inboxes: e-mail and Usenet. I read every e-mail message I received. I read most Usenet postings in the groups I followed, but it was no big deal if I missed some. Those are the two main types of inboxes: the ones where you pay attention to every message, and the ones where you read the interesting ones and skip the others. Other examples of the first kind of inbox, at least for me, are voice mail and the original inbox: personal letters. An example of the second kind of inbox is the daily news, whether on paper or on radio or television.sinopsis film

I didn’t realize it when I was younger, but there is another kind of inbox: what the people you see frequently are talking about. In one sense this is gossip, in another it is society. This is a kind of inbox which you don’t look for, where you don’t pay attention to every message, where information just kind of passes by you. Mostly you glance at it and forget it, although you usually remember the general gist.

In the last several years that kind of inbox has been copied online, most obviously in Facebook and Twitter and their friends. The difference between them and Usenet is organizational. Usenet was organized around specific themes. Sometimes the theme was completely random, but it meant that only people who wanted something random read that group. Facebook and Twitter are organized around social groups or followers, just like gossip.

Because it’s a pain to have to check lots of inboxes, there are lots of tools these days to copy information from one inbox to another, and, conversely, to let you send information to other people’s inboxes in various different ways. These tools all work differently and have various degrees of effectiveness. At the same time, all popular inboxes struggle with a problem of spam: messages that you don’t really want that are mostly trying to part you from your money in some way.

It would be nice if inboxes were easier to consolidate, if I could look at some master control panel and say “I’d like his blog posts to come to this box in my e-mail, and I’d like her most recent photo to my desktop background” and then change all of it again tomorrow. But in real life anybody who created such a panel would get so bogged down in issues of authenticity and spam that the next big thing would never bother to interoperate with the panel, in fact would probably try to actively avoid it so that they could in fact become the next big thing, rather than being just another inbox.

Meanwhile we’ll all just keep juggling our proliferation of inboxes, which mostly means getting better and better at ignoring them, at accepting that we will never catch up with all of them, and that that’s maybe not perfect, but it’s OK, it’s as good as it gets.

Comments (1)

Future Payments

One of the ways that pure capitalism fails is an inability to price limited resources. There is a real sense in which oil, a limited resource, is almost certainly worth more today than people are paying for it. It seems likely that people in the future will be aghast at the way we are wasting this precious resource, one that has taken millions of years to create, by simply burning it to drive a few blocks to the grocery store. Those people in the future would gladly pay far more than $100 a barrel, and their bids should drive the price up. Unfortunately, those people do not yet exist, and their bids don’t count.

Companies can take future pricing into account, of course. However, future prices will always be taken at a discount, due to uncertainty and because it’s better to have money in hand. Also, companies are run by people, and few people take a truly long range view: few people care much about what a company will be like in 150 years. Those people who do take a long range view are rarely chosen to be in charge of company decisions.

Of course there are no pure capitalist societies. Real societies address this issue via some sort of regulation, such as taxing the resource to increase its price, or regulation to limit its use, or a cap-and-trade and system which does both. Not that the U.S. is doing any of those things for oil, but at least there is a possible answer to this flaw of capitalism, an answer that relies on some sort of government.

Comments (8)

.gcc_except_table

Throwing an exception in C++ requires more than unwinding the stack. As the program unwinds, local variable destructors must be executed. Catch clauses must be examined to see if they should catch the exception. Exception specifications must be checked to see if the exception should be redirected to the unexpected handler. Similar issues arise in Go, Java, and even C when using gcc’s cleanup function attribute.

As I described earlier, each CIE in the unwind data may contain a pointer to a personality function, and each FDE may contain a pointer to the LSDA, the Language Specific Data Area. Each language has its own personality function. The LSDA is only used by the personality function, so it could in principle differ for each language. However, at least for gcc, every language uses the same format, since the LSDA is generated by the language-independent middle-end.

The personality function takes five arguments:

  1. A int version number, currently 1.
  2. A bitmask of actions.
  3. An exception class, a 64-bit unsigned integer which is specific to a language.
  4. A pointer to information about the specific exception being thrown.
  5. Unwinder state information.

The exception class permits code written in one language to work correctly when an exception is thrown by code written in a different language. The value for g++ is
“GNUCC++\0” (or “GNUCC++\1” for a dependent exception, which is used when rethrowing an exception). The value for Go is “GNUCGO\0\0”. The exception specific information can only be examined if the exception class is recognized.

Unwinding the stack for an exception is done in two phases. In the first phase, the unwinder walks up the stack passing the action _UA_SEARCH_PHASE (which has the value 1) to each personality function that it finds. The personality function should examine the LSDA to see if there is a handler for the exception being thrown. It should return _URC_HANDLER_FOUND (6) if there is or _URC_CONTINUE_UNWIND (8) if there isn’t. The search phase will continue until a handler is found or until the top of the stack is reached. The unwinder will not actually change anything while walking. If the top of the stack is reached the unwinder will simply return, and the calling code will take the appropriate action, which for C++ is to call std::terminate. Because of the two phase unwinding approach, if std::terminate dumps core, a backtrace will show the code which threw the exception.

If a handler is found, the second phase begins. The unwinder walks up the stack passing the action _UA_CLEANUP_PHASE (2) to each personality function. The unwinder will also set _UA_FORCE_UNWIND (8) in the actions bitmask if the personality function may not catch the exception, because the unwinding is happening due to some event like thread cancellation. The unwinder will walk up the stack until it finds the handler—the stack frame for which the personality function returned _URC_HANDLER_FOUND. When it calls that function, the unwinder will pass _UA_HANDLER_FRAME (4) in the actions bitmask. This time, the unwinder will changes things as it goes, removing stack frames.

In order to run destructors, the personality function will call _Unwind_SetIP on the context parameter to set the program counter to point to the cleanup routine, and then return _URC_INSTALL_CONTEXT (7) to tell the unwinder to branch to the current context. The address which starts the cleanup is known as a landing pad. The cleanup should do whatever it needs to do, and then call _Unwind_Resume. The exception information needs to be passed to _Unwind_Resume. The personality routine arranges to pass the exception information to the cleanup by calling _Unwind_SetGR passing __builtin_eh_return_data_regno(0) and the exception information passed to the personality routine. Each target which supports this approach has to dedicate two registers to holding exception information. This is the first one.

The personality function which finds the handler works pretty much the same way. It may also use _Unwind_SetGR to set a value in __builtin_eh_return_data_regno(1) to indicate which exception was found. The exception handler may rethrow the exception via _Unwind_RaiseException or it may simply continue a normal execution path.

At this point we’ve seen everything except how the personality function decides whether it needs to run a cleanup or catch an exception. The personality function makes this decision based on the LSDA. As mentioned above, while the LSDA could be language dependent, in practice it is not. There is a different personality function for each language, but they all do more or less the same thing, omitting aspects which are not relevant for the language (e.g., there is a personality function for C, but it only runs cleanups and does not bother to look for exception handlers).

The LSDA is found in the section .gcc_except_table (the personality function is just a function and lives in the .text section as usual). The personality function gets a pointer to it by calling _Unwind_GetLanguageSpecificData. The LSDA starts with the following fields:

  1. A 1 byte encoding of the following field (a DW_EH_PE_xxx value).
  2. If the encoding is not DW_EH_PE_omit, the landing pad base. This is the base from which landing pad offsets are computed. If this is omitted, the base comes from calling _Unwind_GetRegionStart, which returns the beginning of the code described by the current FDE. In practice this field is normally omitted.
  3. A 1 byte encoding of the entries in the type table (a DW_EH_PE_xxx value).
  4. If the encoding is not DW_EH_PE_omit, the types table pointer. This is an unsigned LEB128 value, and is the byte offset from this field to the start of the types table used for exception matching.
  5. A 1 byte encoding of the fields in the call-site table (a DW_EH_PE_xxx value).
  6. An unsigned LEB128 value holding the length in bytes of the call-site table.

This header is immediately followed by the call-site table. Each entry in the call-site table has four fields. The number of bytes in the header gives the total length. Each entry in the call-site table describes a particular sequence of instructions within the function that the FDE desribes.

  1. The start of the instructions for the current call site, a byte offset from the landing pad base. This is encoded using the encoding from the header.
  2. The length of the instructions for the current call site, in bytes. This is encoded using the encoding from the header.
  3. A pointer to the landing pad for this sequence of instructions, or 0 if there isn’t one. This is a byte offset from the landing pad base. This is encoded using the encoding from the header.
  4. The action to take, an unsigned LEB128. This is 1 plus a byte offset into the action table. The value zero means that there is no action.

The call-site table is sorted by the start address field. If the personality function finds that there is no entry for the current PC in the call-site table, then there is no exception information. This should not happen in normal operation, and in C++ will lead to a call to std::terminate. If there is an entry in the call-site table, but the landing pad is zero, then there is nothing to do: there are no destructors to run or exceptions to catch. This is a normal case, and the unwinder will simply continue. If the action record is zero, then there are destructors to run but no exceptions to catch. The personality function will arrange to run the destructors as described above, and unwinding will continue.

Otherwise, we have an offset into the action table. Each entry in the action table is a pair of signed LEB128 values. The first number is a type filter. The second number is a byte offset to the next entry in the action table. A byte offset of 0 ends the current set of actions.

A type filter of zero indicates a cleanup, which is the same as an action record of zero in the call-site table. This means that there is a cleanup to be called even if none of the types match.

A positive type filter is an index into the types table. This is a negative index: the value 1 means the entry preceding the types table base, 2 means the entry before that, etc. The size of entries in the types table comes from the encoding in the header, as does the base of the types table. Each entry in the types table is a pointer to a type information structure. If this type information structure matches the type of the exception, then we have found a handler for this exception. The type filter value is a switch value will be passed to the handler in exception register 1. The actual comparison of the type information, and determining the type information from the exception pointer, really is language dependent. In C++ this is a pointer to a std::type_info structure. A NULL pointer in the types table is a catch-all handler.

A negative type filter is a byte offset into the types table of a NULL terminated list of pointers to type information structures. If the type of the current exception does not match any of the entries in the list, then there is an exception specification error. This is treated as an exception handler with a negative switch value.Watch movie online The Transporter Refueled (2015)

I think that covers everything about how gcc unwinds the stack and throws exceptions.

Comments (6)

.eh_frame_hdr

If you followed my last post, you will see that in order to unwind the stack you have to find the FDE associated with a given program counter value. There are two steps to this problem. The first one is finding the CIEs and FDEs at all. The second one is, given the set of FDEs, finding the one you need.

The old way this worked was that gcc would create a global constructor which called the function __register_frame_info, passing a pointer to the .eh_frame data and a pointer to the object. The latter pointer would indicate the shared library, and was used to deregister the information after a dlclose. When looking for an FDE, the unwinder would walk through the registered frames, and sort them. Then it would use the sorted list to find the desired FDE.

The old way still works, but these days, at least on GNU/Linux, the sorting is done at link time, which is better than doing it at runtime. Both gold and the GNU linker support an option --eh-frame-hdr which tell them to construct a header for all the .eh_frame sections. This header is placed in a section named .eh_frame_hdr and also in a PT_GNU_EH_FRAME segment. At runtime the unwinder can find all the PT_GNU_EH_FRAME segments by calling dl_iterate_phdr.

The format of the .eh_frame_hdr section is as follows:

  1. A 1 byte version number, currently 1.
  2. A 1 byte encoding of the pointer to the exception frames. This is a DW_EH_PE_xxx value. It is normally DW_EH_PE_pcrel | DW_EH_PE_sdata4, meaning a 4 byte relative offset.
  3. A 1 byte encoding of the count of the number of FDEs in the lookup table. This is a DW_EH_PE_xxx value. It is normally DW_EH_PE_udata4, meaning a 4 byte unsigned count.
  4. A 1 byte encoding of the entries in the lookup table. This is a DW_EH_PE_xxx value. It is normally DW_EH_PE_datarel | DW_EH_PE_sdata4, meaning a 4 byte offset from the start of the .eh_frame_hdr section. That is the only encoding that gcc’s current unwind library supports.
  5. A pointer to the contents of the .eh_frame section, encoded as indicated by the second byte in the header. This pointer is only used if the format of the lookup table is not supported or is for some reason omitted..
  6. The number of FDE pointers in the table, encoded as indicated by the third byte in the header. If there are no FDEs, the encoding can be DW_EH_PE_omit and this number will not be present.
  7. The lookup table itself, starting at a 4-byte aligned address in memory. Assuming the fourth byte in the header is DW_EH_PE_datarel | DW_EH_PE_sdata4, each entry in the table is 8 bytes long. The first four bytes are an offset to the initial PC value for the FDE. The last four byte are an offset to the FDE data itself. The table is sorted by starting PC.

Since FDEs do not overlap, this table is sufficient for the stack unwinder to quickly find the relevant FDE if there is one.

Comments

.eh_frame

When gcc generates code that handles exceptions, it produces tables that describe how to unwind the stack. These tables are found in the .eh_frame section. The format of the .eh_frame section is very similar to the format of a DWARF .debug_frame section. Unfortunately, it is not precisely identical. I don’t know of any documentation which describes this format. The following should be read in conjunction with the relevant section of the DWARF standard, available from http://dwarfstd.org.

The .eh_frame section is a sequence of records. Each record is either a CIE (Common Information Entry) or an FDE (Frame Description Entry). In general there is one CIE per object file, and each CIE is associated with a list of FDEs. Each FDE is typically associated with a single function. The CIE and the FDE together describe how to unwind to the caller if the current instruction pointer is in the range covered by the FDE.

There should be exactly one FDE covering each instruction which may be being executed when an exception occurs. By default an exception can only occur during a function call or a throw. When using the -fnon-call-exceptions gcc option, an exception can also occur on most memory references and floating point operations. When using -fasynchronous-unwind-tables, the FDE will cover every instruction, to permit unwinding from a signal handler.

The general format of a CIE or FDE starts as follows:

  1. Length of record. Read 4 bytes. If they are not 0xffffffff, they are the length of the CIE or FDE record. Otherwise the next 64 bits holds the length, and this is a 64-bit DWARF format. This is like .debug_frame.
  2. A 4 byte ID. For a CIE this is 0. For an FDE it is the byte offset from this field to the start of the CIE with which this FDE is associated. The byte offset goes to the length record of the CIE. A positive value goes backward; that is, you have to subtract the value of the ID field from the current byte position to get the CIE position. This differs from .debug_frame in that the offset is relative rather than being an offset into the .debug_frame section.

A CIE record continues as follows:

  1. 1 byte CIE version. As of this writing this should be 1 or 3.
  2. NUL terminated augmentation string. This is a sequence of characters. Very old versions of gcc used the string “eh” here, but I won’t document that. This is described further below.
  3. Code alignment factor, an unsigned LEB128 (LEB128 is a DWARF encoding for numbers which I won’t describe here). This is a constant factored out of offset instructions, as in .debug_frame.
  4. Data alignment factor, a signed LEB128. This is a constant factored out of offset instructions, as in .debug_frame.
  5. The return address register. In CIE version 1 this is a single byte; in CIE version 3 this is an unsigned LEB128. This indicates which column in the frame table represents the return address.

The next fields of the CIE depend on the augmentation string.

  • If the augmentation string starts with ‘z’, we now find an unsigned LEB128 which is the length of the augmentation data, rounded up so that the CIE ends on an address boundary. This is used to skip to the end of the augmentation data if an unrecognized augmentation character is seen.
  • If the next character in the augmentation string is ‘L’, the next byte in the CIE is the LSDA (Language Specific Data Area) encoding. This is a DW_EH_PE_xxx value (described later). The default is DW_EH_PE_absptr.
  • If the next character in the augmentation string is ‘R’, the next byte in the CIE is the FDE encoding. This is a DW_EH_PE_xxx value. The default is DW_EH_PE_absptr.
  • The character ‘S’ in the augmentation string means that this CIE represents a stack frame for the invocation of a signal handler. When unwinding the stack, signal stack frames are handled slightly differently: the instruction pointer is assumed to be before the next instruction to execute rather than after it.
  • If the next character in the augmentation string is ‘P’, the next byte in the CIE is the personality encoding, a DW_EH_PE_xxx value. This is followed by a pointer to the personality function, encoded using the personality encoding. I’ll describe the personality function some other day.

The remaining bytes are an array of DW_CFA_xxx opcodes which define the initial values for the frame table. This is then followed by DW_CFA_nop padding bytes as required to match the total length of the CIE.

An FDE starts with the length and ID described above, and then continues as follows.

  1. The starting address to which this FDE applies. This is encoded using the FDE encoding specified by the associated CIE.
  2. The number of bytes after the start address to which this FDE applies. This is encoded using the FDE encoding.
  3. If the CIE augmentation string starts with ‘z’, the FDE next has an unsigned LEB128 which is the total size of the FDE augmentation data. This may be used to skip data associated with unrecognized augmentation characters.
  4. If the CIE does not specify DW_EH_PE_omit as the LSDA encoding, the FDE next has a pointer to the LSDA, encoded as specified by the CIE.

The remaining bytes in the FDE are an array of DW_CFA_xxx opcodes which set values in the frame table for unwinding to the caller.

The DW_EH_PE_xxx encodings describe how to encode values in a CIE or FDE. The basic encoding is as follows:

  • DW_EH_PE_absptr = 0x00: An absolute pointer. The size is determined by whether this is a 32-bit or 64-bit address space, and will be 32 or 64 bits.
  • DW_EH_PE_omit = 0xff: The value is omitted.
  • DW_EH_PE_uleb128 = 0x01: The value is an unsigned LEB128.
  • DW_EH_PE_udata2 = 0x02, DW_EH_PE_udata4 = 0x03, DW_EH_PE_udata8 = 0x04: The value is stored as unsigned data with the specified number of bytes.
  • DW_EH_PE_signed = 0x08: A signed number. The size is determined by whether this is a 32-bit or 64-bit address space. I don’t think this ever appears in a CIE or FDE in practice.
  • DW_EH_PE_sleb128 = 0x09: A signed LEB128. Not used in practice.
  • DW_EH_PE_sdata2 = 0x0a, DW_EH_PE_sdata4 = 0x0b, DW_EH_PE_sdata8 = 0x0c: The value is stored as signed data with the specified number of bytes. Not used in practice.

In addition the above basic encodings, there are modifiers.

  • DW_EH_PE_pcrel = 0x10: Value is PC relative.
  • DW_EH_PE_textrel = 0x20: Value is text relative.
  • DW_EH_PE_datarel = 0x30: Value is data relative.
  • DW_EH_PE_funcrel = 0x40: Value is relative to start of function.
  • DW_EH_PE_aligned = 0x50: Value is aligned: padding bytes are inserted as required to make value be naturally aligned.
  • DW_EH_PE_indirect = 0x80: This is actually the address of the real value.

If you follow all that, and also read up on .debug_frame, then you have enough information to unwind the stack at runtime, e.g. to implement glibc’s backtrace function. Later I’ll describe the LSDA and the personality function, which work together to implement exception catching on top of stack unwinding.

Comments (7)

« Previous entries Next Page » Next Page »