[Xcb] _Problems_ in GSoC, 2011

[Jamey Sharp]

On Mon, Jul 04, 2011 at 03:42:24AM +0530, vikash agrawal wrote:
> Also it has been long I am trying to patch a bug, I had several discussion
> with pharris ( I apologise for pestering you so much ) over the same. I am
> still studying c_client.py and a quick glance of it reveals
> '_c_serialize_helper_insert_  function', with context being sizeof, is
> responsible for xcb_str_sizeof in xproto.c. So I believe this might need
> some hacks.
> Also, if I am not wrong there is a problem with xcb_str_next with respect
> master and 1.7, but for this I have a very n00b and basic idea like if
> self.c_next_name == 'xcb_str_next': # and then necessary conditions of
> _c('whatever'); might solve the purpose. If this feels a way then can we
> specifically do the same for other buggy issues.

I'm sorry to say, the problem is not specific to xcb_str_next or to
strings at all. The good news is that it should be solvable in a general
way, without hacks for specific types. I wrote some about this here:

http://lists.freedesktop.org/archives/xcb/2011-March/006837.html

Here is a sketch of an algorithm that I believe is correct for
statically computing alignment padding for all X types. I'll use the
terms from xcbgen/xtypes.py.

First, compute the minimum alignment requirement for every type:

- For every SimpleType and ExprType, including the standard types like
  CARD8, the alignment required equals the size of the type, but no more
  than 4 bytes. So CARD8 needs 1 byte, INT16 needs 2 bytes, FLOAT needs
  4 bytes, and DOUBLE also needs 4 bytes.

- For ListTypes, the alignment is the same as the member type's
  alignment.

- Request, Reply, Event, and Error types always have 4-byte alignment.

- For StructType and UnionType, the alignment is the maximum alignment
  needed by any field in the struct or union. So STR, which is a struct
  containing a CARD8 and a list of CARD8, only needs 1-byte alignment;
  but a struct containing an INT16 and a DOUBLE needs 4-byte alignment.

I haven't thought about the rules for Switch or Bitcase yet.

I think implementing the above in proto/xcbgen would be a good target
for something to finish by the time of the mid-term review. The rest of
the algorithm is below.

Once you know the alignment of every type, you can insert correct
padding. Only ComplexTypes actually insert padding anywhere.

You need to keep track of the byte offset of every field in a complex
type, modulo 4. The first field in a complex type is at offset 0.

For each field you add, first check whether its alignment requirements
are met, and if not, insert padding. So if you try to add a CARD16,
which has 2-byte alignment, at offset 1, then you need 1 byte of
padding. To add a CARD32, needing 4-byte alignment, at offset 1, you
need 3 bytes of padding.

Once you've added any needed padding, add the field itself. Then the new
byte offset is the old offset, plus the padding, plus the size of the
field, mod 4.

After you've added all the fields, insert final padding for the
alignment of the ComplexType itself. If this was a struct that had a
CARD32 field in it, or it was a Request/Reply/Event/Error, then you need
to make sure the final byte offset, mod 4, is 0. If its maximum
alignment was 2, then the final byte offset mod 2 must be 0. This
ensures that a list of values of this type has correct padding between
the members.

The spot where this is a little difficult is if the complex type
contains a list or a variable-length structure. The easy case is when a
field has 4-byte alignment: Then you know that no matter what its length
turns out to be, afterward the byte offset (mod 4) is always 0.

Otherwise, the byte offset after adding the field is not a constant, but
a (potentially complicated) expression. For example, if the field is a
list of fixed-size members, then you need to add sizeof(member) times
the list's expression. You'll eventually emit these complicated byte
offset expressions into the generated C code, when inserting padding for
some following field.

At that point I think the bug will be fixed, and we'll be quite pleased
with your Summer of Code project. :-) But there's one more improvement:

Since we only care about the byte offset mod 4, many complicated byte
offset expressions can be simplified. For example, if there are two
lists of CARD16s in a row that both use the same length expression, then
you might construct this byte offset expression:
	old_offset + ((2 * length) + (2 * length)) % 4
But that turns out to just equal "old_offset", because (4 * x) % 4 == 0
for all x. This is a generalization of the above case where fields with
4-byte alignment always result in a byte offset of 0.

I hope that helps!
Jamey
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.freedesktop.org/archives/xcb/attachments/20110704/3d0f4f80/attachment-0001.pgp>