[Xcb] [PATCH proto 4/5] automatic alignment checker / manual offsets
Christian Linhart
chris at demorecorder.com
Sun Nov 1 09:26:33 PST 2015
The verification algorithm basically traverses the protocol-description
of a protocol entity by recursively processing all fields and their
types.
A start-align consists of two numbers:
* the alignment: This is a power of 2, and guarantees that the
address (or protocol position) minus the offset can be divided
by this number.
* the offset: how many bytes the current position is after a
position that can be divided by the alignment.
The algorithm starts with the start-alignment and computes the alignment
of each field from the start-align of the previous field as follows:
* if the previous field is a primitive type then the offset is increased
by the size of the primitive type module the alignment.
If the alignment or offset are incompatible with the primitive type,
then an error is reported.
* if the previous field is a complex type, then it is processed recursively.
* if the previous field is an alignment-pad, then the alignment is
adjusted accordingly, as to be expected by the alignment-pad.
Start-aligns can also be set manually with the xml-element
"required_start_align" which has two attributes: "align" and "offset"
If "offset" is omitted, it is assumed to 0.
All toplevel protocol entities default to 4-byte start-alignment with offset 0.
All non-toplevel complex entities, such as structs, switch, case, ...
do not have a default alignment.
If no alignment is explicitly specified for them, their alignment
is computed by their usage in other entities.
In that case, if they are used with aligments that violate the
alignment requirements of some of their fields, an error is issued.
If they are used with an alignment with non-zero offset,
a warning is issued, which recommends to specify the required_start_align
explicitly. (Reason: I don't want non-zero offsets to be silently
computed automatically. These non-zero offsets have to be reviewed
by a human and specified explicitely to record that this was reviewed
by a human)
If the required_start_align is explicitly specified for an entity
then an error will be issued if it is used with an aligment that's
incompatible with the explicitly specified alignment.
If an entity is used in different contexts with different start-aligns
then those start-aligns are combined to an align which is compatible
with all aligns.
E.g. (align 4, offset 0) and (align 4, offset 2) are combined
to (align 2, offset 0).
Error reports include the relevant context for a misalignment.
For non-toplevel entities this includes the entity-usage stack.
There is some complexity in the algorithm for reducing the size
of the error-reports to include only the relevant info.
This alignment verifier is also a prerequisite for getting
rid of implicit alignment altogether.
(This will then simplify the generated code and make it faster.)
Signed-off-by: Christian Linhart <chris at demorecorder.com>
---
xcbgen/Makefile.am | 2 +-
xcbgen/align.py | 177 +++++++++++++++++
xcbgen/expr.py | 26 +++
xcbgen/xtypes.py | 575 +++++++++++++++++++++++++++++++++++++++++++++++++++--
4 files changed, 757 insertions(+), 23 deletions(-)
create mode 100644 xcbgen/align.py
diff --git a/xcbgen/Makefile.am b/xcbgen/Makefile.am
index 110a992..d6c7adc 100644
--- a/xcbgen/Makefile.am
+++ b/xcbgen/Makefile.am
@@ -1,3 +1,3 @@
pkgpythondir = $(pythondir)/xcbgen
-pkgpython_PYTHON = __init__.py error.py expr.py matcher.py state.py xtypes.py
+pkgpython_PYTHON = __init__.py error.py expr.py align.py matcher.py state.py xtypes.py
diff --git a/xcbgen/align.py b/xcbgen/align.py
new file mode 100644
index 0000000..dbac148
--- /dev/null
+++ b/xcbgen/align.py
@@ -0,0 +1,177 @@
+'''
+This module contains helper classes for alignment arithmetic and checks
+'''
+
+from fractions import gcd
+
+class Alignment(object):
+
+ def __init__(self, align=4, offset=0):
+ self.align = align
+ # normalize the offset (just in case)
+ self.offset = offset % align
+
+
+ def __eq__(self, other):
+ return self.align == other.align and self.offset == other.offset
+
+ def __str__(self):
+ return "(align=%d, offset=%d)" % (self.align, self.offset)
+
+ @staticmethod
+ def for_primitive_type(size):
+ # compute the required start_alignment based on the size of the type
+ if size % 8 == 0:
+ # do 8-byte primitives require 8-byte alignment in X11?
+ return Alignment(8,0)
+ elif size % 4 == 0:
+ return Alignment(4,0)
+ elif size % 2 == 0:
+ return Alignment(2,0)
+ else:
+ return Alignment(1,0)
+
+
+ def align_after_fixed_size(self, size):
+ new_offset = (self.offset + size) % self.align
+ return Alignment(self.align, new_offset)
+
+
+ def is_guaranteed_at(self, external_align):
+ '''
+ Assuming the given external_align, checks whether
+ self is fulfilled for all cases.
+ Returns True if yes, False otherwise.
+ '''
+ if self.align == 1 and self.offset == 0:
+ # alignment 1 with offset 0 is always fulfilled
+ return True
+
+ if external_align is None:
+ # there is no external align -> fail
+ return False
+
+ if external_align.align < self.align:
+ # the external align guarantees less alignment -> not guaranteed
+ return False
+
+ if external_align.align % self.align != 0:
+ # the external align cannot be divided by our align
+ # -> not guaranteed
+ # (this can only happen if there are alignments that are not
+ # a power of 2, which is highly discouraged. But better be
+ # safe and check for it)
+ return False
+
+ if external_align.offset % self.align != self.offset:
+ # offsets do not match
+ return False
+
+ return True
+
+
+ def combine_with(self, other):
+ # returns the alignment that is guaranteed when
+ # both, self or other, can happen
+ new_align = gcd(self.align, other.align)
+ new_offset_candidate1 = self.offset % new_align
+ new_offset_candidate2 = other.offset % new_align
+ if new_offset_candidate1 == new_offset_candidate2:
+ new_offset = new_offset_candidate1
+ else:
+ offset_diff = abs(new_offset_candidate2 - new_offset_candidate1)
+ new_align = gcd(new_align, offset_diff)
+ new_offset_candidate1 = self.offset % new_align
+ new_offset_candidate2 = other.offset % new_align
+ assert new_offset_candidate1 == new_offset_candidate2
+ new_offset = new_offset_candidate1
+ # return the result
+ return Alignment(new_align, new_offset)
+
+
+class AlignmentLog(object):
+
+ def __init__(self):
+ self.ok_list = []
+ self.fail_list = []
+ self.verbosity = 1
+
+ def __str__(self):
+ result = ""
+
+ # output the OK-list
+ for (align_before, field_name, type_obj, callstack, align_after) in self.ok_list:
+ stacksize = len(callstack)
+ indent = ' ' * stacksize
+ if self.ok_callstack_is_relevant(callstack):
+ if field_name is None or field_name == "":
+ result += (" %sok: %s:\n\t%sbefore: %s, after: %s\n"
+ % (indent, str(type_obj), indent, str(align_before), str(align_after)))
+ else:
+ result += (" %sok: field \"%s\" in %s:\n\t%sbefore: %s, after: %s\n"
+ % (indent, str(field_name), str(type_obj),
+ indent, str(align_before), str(align_after)))
+ if self.verbosity >= 1:
+ result += self.callstack_to_str(indent, callstack)
+
+ # output the fail-list
+ for (align_before, field_name, type_obj, callstack, reason) in self.fail_list:
+ stacksize = len(callstack)
+ indent = ' ' * stacksize
+ if field_name is None or field_name == "":
+ result += (" %sfail: align %s is incompatible with\n\t%s%s\n\t%sReason: %s\n"
+ % (indent, str(align_before), indent, str(type_obj), indent, reason))
+ else:
+ result += (" %sfail: align %s is incompatible with\n\t%sfield \"%s\" in %s\n\t%sReason: %s\n"
+ % (indent, str(align_before), indent, str(field_name), str(type_obj), indent, reason))
+
+ if self.verbosity >= 1:
+ result += self.callstack_to_str(indent, callstack)
+
+
+ return result
+
+
+ def callstack_to_str(self, indent, callstack):
+ result = "\t%scallstack: [\n" % indent
+ for stack_elem in callstack:
+ result += "\t %s%s\n" % (indent, str(stack_elem))
+ result += "\t%s]\n" % indent
+ return result
+
+
+ def ok_callstack_is_relevant(self, ok_callstack):
+ # determine whether an ok callstack is relevant for logging
+ if self.verbosity >= 2:
+ return True
+
+ # empty callstacks are always relevant
+ if len(ok_callstack) == 0:
+ return True
+
+ # check whether the ok_callstack is a subset or equal to a fail_callstack
+ for (align_before, field_name, type_obj, fail_callstack, reason) in self.fail_list:
+ if len(ok_callstack) <= len(fail_callstack):
+ zipped = zip(ok_callstack, fail_callstack[:len(ok_callstack)])
+ is_subset = all([i == j for i, j in zipped])
+ if is_subset:
+ return True
+
+ return False
+
+
+ def ok(self, align_before, field_name, type_obj, callstack, align_after):
+ self.ok_list.append((align_before, field_name, type_obj, callstack, align_after))
+
+ def fail(self, align_before, field_name, type_obj, callstack, reason):
+ self.fail_list.append((align_before, field_name, type_obj, callstack, reason))
+
+ def append(self, other):
+ self.ok_list.extend(other.ok_list)
+ self.fail_list.extend(other.fail_list)
+
+ def ok_count(self):
+ return len(self.ok_list)
+
+
+
diff --git a/xcbgen/expr.py b/xcbgen/expr.py
index e4ee8c6..a716d34 100644
--- a/xcbgen/expr.py
+++ b/xcbgen/expr.py
@@ -20,14 +20,25 @@ class Field(object):
self.enum = enum
self.visible = visible
self.wire = wire
self.auto = auto
self.isfd = isfd
self.parent = None
+ def __str__(self):
+ field_string = "Field"
+ if self.field_name is None:
+ if self.field_type is not None:
+ field_string += " with type " + str(self.type)
+ else:
+ field_string += " \"" + self.field_name + "\""
+ if self.parent is not None:
+ field_string += " in " + str(self.parent)
+
+ return field_string
class Expression(object):
'''
Represents a mathematical expression for a list length or exprfield.
Public fields:
op is the operation (text +,*,/,<<,~) or None.
@@ -118,14 +129,29 @@ class Expression(object):
else:
# Notreached
raise Exception("undefined tag '%s'" % elt.tag)
def fixed_size(self):
return self.nmemb != None
+ def get_value(self):
+ return self.nmemb
+
+ # if the value of the expression is a guaranteed multiple of a number
+ # return this number, else return 1 (which is trivially guaranteed for integers)
+ def get_multiple(self):
+ multiple = 1
+ if self.op == '*':
+ if self.lhs.fixed_size():
+ multiple *= self.lhs.get_value()
+ if self.rhs.fixed_size():
+ multiple *= self.rhs.get_value()
+
+ return multiple
+
def recursive_resolve_tasks(self, module, parents):
for subexpr in (self.lhs, self.rhs):
if subexpr != None:
subexpr.recursive_resolve_tasks(module, parents)
self.contains_listelement_ref |= subexpr.contains_listelement_ref
def resolve(self, module, parents):
diff --git a/xcbgen/xtypes.py b/xcbgen/xtypes.py
index 4d6bbc0..f5302be 100644
--- a/xcbgen/xtypes.py
+++ b/xcbgen/xtypes.py
@@ -1,13 +1,16 @@
'''
This module contains the classes which represent XCB data types.
'''
from xcbgen.expr import Field, Expression
+from xcbgen.align import Alignment, AlignmentLog
import __main__
+verbose_align_log = False
+
class Type(object):
'''
Abstract base class for all XCB data types.
Contains default fields, and some abstract methods.
'''
def __init__(self, name):
'''
@@ -32,14 +35,18 @@ class Type(object):
self.is_reply = False
self.is_union = False
self.is_pad = False
self.is_switch = False
self.is_case_or_bitcase = False
self.is_bitcase = False
self.is_case = False
+ self.required_start_align = Alignment()
+
+ # the biggest align value of an align-pad contained in this type
+ self.max_align_pad = 1
def resolve(self, module):
'''
Abstract method for resolving a type.
This should make sure any referenced types are already declared.
'''
raise Exception('abstract resolve method not overridden!')
@@ -87,34 +94,114 @@ class Type(object):
for (idx, field) in enumerate(complex_type.fields):
if field == _placeholder_byte:
complex_type.fields[idx] = new_fd
return
complex_type.fields.append(new_fd)
-class SimpleType(Type):
+
+ def get_total_size(self):
+ '''
+ get the total size of this type if it is fixed-size, otherwise None
+ '''
+ if self.fixed_size():
+ if self.nmemb is None:
+ return self.size
+ else:
+ return self.size * self.nmemb
+ else:
+ return None
+
+ def get_align_offset(self):
+ if self.required_start_align is None:
+ return 0
+ else:
+ return self.required_start_align.offset
+
+ def is_acceptable_start_align(self, start_align, callstack, log):
+ return self.get_alignment_after(start_align, callstack, log) is not None
+
+ def get_alignment_after(self, start_align, callstack, log):
+ '''
+ get the alignment after this type based on the given start_align.
+ the start_align is checked for compatibility with the
+ internal start align. If it is not compatible, then None is returned
+ '''
+ if self.required_start_align is None or self.required_start_align.is_guaranteed_at(start_align):
+ return self.unchecked_get_alignment_after(start_align, callstack, log)
+ else:
+ if log is not None:
+ log.fail(start_align, "", self, callstack + [self],
+ "start_align is incompatible with required_start_align %s"
+ % (str(self.required_start_align)))
+ return None
+
+ def unchecked_get_alignment_after(self, start_align, callstack, log):
+ '''
+ Abstract method for geting the alignment after this type
+ when the alignment at the start is given, and when this type
+ has variable size.
+ '''
+ raise Exception('abstract unchecked_get_alignment_after method not overridden!')
+
+
+ @staticmethod
+ def type_name_to_str(type_name):
+ if isinstance(type_name, str):
+ #already a string
+ return type_name
+ else:
+ return ".".join(type_name)
+
+
+ def __str__(self):
+ return type(self).__name__ + " \"" + Type.type_name_to_str(self.name) + "\""
+
+class PrimitiveType(Type):
+
+ def __init__(self, name, size):
+ Type.__init__(self, name)
+ self.size = size
+ self.nmemb = 1
+
+ # compute the required start_alignment based on the size of the type
+ self.required_start_align = Alignment.for_primitive_type(self.size)
+
+ def unchecked_get_alignment_after(self, start_align, callstack, log):
+ my_callstack = callstack + [self];
+ after_align = start_align.align_after_fixed_size(self.size)
+
+ if log is not None:
+ if after_align is None:
+ log.fail(start_align, "", self, my_callstack,
+ "align after fixed size %d failed" % self.size)
+ else:
+ log.ok(start_align, "", self, my_callstack, after_align)
+
+ return after_align
+
+ def fixed_size(self):
+ return True
+
+class SimpleType(PrimitiveType):
'''
Derived class which represents a cardinal type like CARD32 or char.
Any type which is typedef'ed to cardinal will be one of these.
Public fields added:
none
'''
def __init__(self, name, size):
- Type.__init__(self, name)
+ PrimitiveType.__init__(self, name, size)
self.is_simple = True
- self.size = size
- self.nmemb = 1
+
def resolve(self, module):
self.resolved = True
- def fixed_size(self):
- return True
-
out = __main__.output['simple']
# Cardinal datatype globals. See module __init__ method.
tcard8 = SimpleType(('uint8_t',), 1)
tcard16 = SimpleType(('uint16_t',), 2)
tcard32 = SimpleType(('uint32_t',), 4)
@@ -185,14 +272,16 @@ class ListType(Type):
if elt.tag == 'list':
elts = list(elt)
self.expr = Expression(elts[0] if len(elts) else elt, self)
self.size = member.size if member.fixed_size() else None
self.nmemb = self.expr.nmemb if self.expr.fixed_size() else None
+ self.required_start_align = self.member.required_start_align
+
def make_member_of(self, module, complex_type, field_type, field_name, visible, wire, auto, enum=None):
if not self.fixed_size():
# We need a length field.
# Ask our Expression object for it's name, type, and whether it's on the wire.
lenfid = self.expr.lenfield_type
lenfield_name = self.expr.lenfield_name
lenwire = self.expr.lenwire
@@ -215,54 +304,114 @@ class ListType(Type):
def resolve(self, module):
if self.resolved:
return
self.member.resolve(module)
self.expr.resolve(module, self.parents)
+ self.required_start_align = self.member.required_start_align
+
# Find my length field again. We need the actual Field object in the expr.
# This is needed because we might have added it ourself above.
if not self.fixed_size():
for parent in self.parents:
for field in parent.fields:
if field.field_name == self.expr.lenfield_name and field.wire:
self.expr.lenfield = field
break
self.resolved = True
def fixed_size(self):
return self.member.fixed_size() and self.expr.fixed_size()
-class ExprType(Type):
+ def unchecked_get_alignment_after(self, start_align, callstack, log):
+ my_callstack = callstack[:]
+ my_callstack.append(self)
+ if start_align is None:
+ log.fail(start_align, "", self, my_callstack, "start_align is None")
+ return None
+ if self.expr.fixed_size():
+ # fixed number of elements
+ num_elements = self.nmemb
+ prev_alignment = None
+ alignment = start_align
+ while num_elements > 0:
+ if alignment is None:
+ if log is not None:
+ log.fail(start_align, "", self, my_callstack,
+ ("fixed size list with size %d after %d iterations"
+ + ", at transition from alignment \"%s\"")
+ % (self.nmemb,
+ (self.nmemb - num_elements),
+ str(prev_alignment)))
+ return None
+ prev_alignment = alignment
+ alignment = self.member.get_alignment_after(prev_alignment, my_callstack, log)
+ num_elements -= 1
+ if log is not None:
+ log.ok(start_align, "", self, my_callstack, alignment)
+ return alignment
+ else:
+ # variable number of elements
+ # check whether the number of elements is a multiple
+ multiple = self.expr.get_multiple()
+ assert multiple > 0
+
+ # iterate until the combined alignment does not change anymore
+ alignment = start_align
+ while True:
+ prev_multiple_alignment = alignment
+ # apply "multiple" amount of changes sequentially
+ prev_alignment = alignment
+ for multiple_count in range(0, multiple):
+
+ after_alignment = self.member.get_alignment_after(prev_alignment, my_callstack, log)
+ if after_alignment is None:
+ if log is not None:
+ log.fail(start_align, "", self, my_callstack,
+ ("variable size list "
+ + "at transition from alignment \"%s\"")
+ % (str(prev_alignment)))
+ return None
+
+ prev_alignment = after_alignment
+
+ # combine with the cumulatively combined alignment
+ # (to model the variable number of entries)
+ alignment = prev_multiple_alignment.combine_with(after_alignment)
+
+ if alignment == prev_multiple_alignment:
+ # does not change anymore by adding more potential elements
+ # -> finished
+ if log is not None:
+ log.ok(start_align, "", self, my_callstack, alignment)
+ return alignment
+
+class ExprType(PrimitiveType):
'''
Derived class which represents an exprfield. Fixed size.
Public fields added:
expr is an Expression object containing the value of the field.
'''
def __init__(self, elt, member, *parents):
- Type.__init__(self, member.name)
+ PrimitiveType.__init__(self, member.name, member.size)
self.is_expr = True
self.member = member
self.parents = parents
self.expr = Expression(list(elt)[0], self)
- self.size = member.size
- self.nmemb = 1
-
def resolve(self, module):
if self.resolved:
return
self.member.resolve(module)
self.resolved = True
- def fixed_size(self):
- return True
class PadType(Type):
'''
Derived class which represents a padding field.
'''
def __init__(self, elt):
Type.__init__(self, tcard8.name)
@@ -270,20 +419,55 @@ class PadType(Type):
self.size = 1
self.nmemb = 1
self.align = 1
if elt != None:
self.nmemb = int(elt.get('bytes', "1"), 0)
self.align = int(elt.get('align', "1"), 0)
+ # pads don't require any alignment at their start
+ self.required_start_align = Alignment(1,0)
+
def resolve(self, module):
self.resolved = True
def fixed_size(self):
return self.align <= 1
+ def unchecked_get_alignment_after(self, start_align, callstack, log):
+ if self.align <= 1:
+ # fixed size pad
+ after_align = start_align.align_after_fixed_size(self.get_total_size())
+ if log is not None:
+ if after_align is None:
+ log.fail(start_align, "", self, callstack,
+ "align after fixed size pad of size %d failed" % self.size)
+ else:
+ log.ok(start_align, "", self, callstack, after_align)
+
+ return after_align
+
+ # align-pad
+ assert self.align > 1
+ assert self.size == 1
+ assert self.nmemb == 1
+ if (start_align.offset == 0
+ and self.align <= start_align.align
+ and start_align.align % self.align == 0):
+ # the alignment pad is size 0 because the start_align
+ # is already sufficiently aligned -> return the start_align
+ after_align = start_align
+ else:
+ # the alignment pad has nonzero size -> return the alignment
+ # that is guaranteed by it, independently of the start_align
+ after_align = Alignment(self.align, 0)
+
+ if log is not None:
+ log.ok(start_align, "", self, callstack, after_align)
+
+ return after_align
class ComplexType(Type):
'''
Derived class which represents a structure. Base type for all structure types.
Public fields added:
fields is an array of Field objects describing the structure fields.
@@ -294,14 +478,26 @@ class ComplexType(Type):
self.elt = elt
self.fields = []
self.nmemb = 1
self.size = 0
self.lenfield_parent = [self]
self.fds = []
+ # get required_start_alignment
+ required_start_align_element = elt.find("required_start_align")
+ if required_start_align_element is None:
+ # unknown -> mark for autocompute
+ self.required_start_align = None
+ else:
+ self.required_start_align = Alignment(
+ int(required_start_align_element.get('align', "4"), 0),
+ int(required_start_align_element.get('offset', "0"), 0))
+ if verbose_align_log:
+ print "Explicit start-align for %s: %s\n" % (self, self.required_start_align)
+
def resolve(self, module):
if self.resolved:
return
enum = None
# Resolve all of our field datatypes.
for child in list(self.elt):
@@ -348,34 +544,180 @@ class ComplexType(Type):
# Get the full type name for the field
field_type = module.get_type_name(fkey)
# Add the field to ourself
type.make_member_of(module, self, field_type, field_name, visible, True, False, enum)
# Recursively resolve the type (could be another structure, list)
type.resolve(module)
+ # Compute the size of the maximally contain align-pad
+ if type.max_align_pad > self.max_align_pad:
+ self.max_align_pad = type.max_align_pad
+
+ self.check_implicit_fixed_size_part_aligns();
+
self.calc_size() # Figure out how big we are
+ self.calc_or_check_required_start_align()
+
self.resolved = True
def calc_size(self):
self.size = 0
for m in self.fields:
if not m.wire:
continue
if m.type.fixed_size():
- self.size = self.size + (m.type.size * m.type.nmemb)
+ self.size = self.size + m.type.get_total_size()
else:
self.size = None
break
+ def calc_or_check_required_start_align(self):
+ if self.required_start_align is None:
+ # no required-start-align configured -> calculate it
+ log = AlignmentLog()
+ callstack = []
+ self.required_start_align = self.calc_minimally_required_start_align(callstack, log)
+ if self.required_start_align is None:
+ print ("ERROR: could not calc required_start_align of %s\nDetails:\n%s"
+ % (str(self), str(log)))
+ else:
+ if verbose_align_log:
+ print ("calc_required_start_align: %s has start-align %s"
+ % (str(self), str(self.required_start_align)))
+ print "Details:\n" + str(log)
+ if self.required_start_align.offset != 0:
+ print (("WARNING: %s\n\thas start-align with non-zero offset: %s"
+ + "\n\tsuggest to add explicit definition with:"
+ + "\n\t\t<required_start_align align=\"%d\" offset=\"%d\" />"
+ + "\n\tor to fix the xml so that zero offset is ok\n")
+ % (str(self), self.required_start_align,
+ self.required_start_align.align,
+ self.required_start_align.offset))
+ else:
+ # required-start-align configured -> check it
+ log = AlignmentLog()
+ callstack = []
+ if not self.is_possible_start_align(self.required_start_align, callstack, log):
+ print ("ERROR: required_start_align %s of %s causes problems\nDetails:\n%s"
+ % (str(self.required_start_align), str(self), str(log)))
+
+
+ def calc_minimally_required_start_align(self, callstack, log):
+ # calculate the minimally required start_align that causes no
+ # align errors
+ best_log = None
+ best_failed_align = None
+ for align in [1,2,4,8]:
+ for offset in range(0,align):
+ align_candidate = Alignment(align, offset)
+ if verbose_align_log:
+ print "trying %s for %s" % (str(align_candidate), str(self))
+ my_log = AlignmentLog()
+ if self.is_possible_start_align(align_candidate, callstack, my_log):
+ log.append(my_log)
+ if verbose_align_log:
+ print "found start-align %s for %s" % (str(align_candidate), str(self))
+ return align_candidate
+ else:
+ my_ok_count = my_log.ok_count()
+ if (best_log is None
+ or my_ok_count > best_log.ok_count()
+ or (my_ok_count == best_log.ok_count()
+ and align_candidate.align > best_failed_align.align)
+ and align_candidate.align != 8):
+ best_log = my_log
+ best_failed_align = align_candidate
+
+
+
+ # none of the candidates applies
+ # this type has illegal internal aligns for all possible start_aligns
+ if verbose_align_log:
+ print "didn't find start-align for %s" % str(self)
+ log.append(best_log)
+ return None
+
+ def is_possible_start_align(self, align, callstack, log):
+ if align is None:
+ return False
+ if (self.max_align_pad > align.align
+ or align.align % self.max_align_pad != 0):
+ # our align pad implementation depends on known alignment
+ # at the start of our type
+ return False
+
+ return self.get_alignment_after(align, callstack, log) is not None
+
def fixed_size(self):
for m in self.fields:
if not m.type.fixed_size():
return False
return True
+
+ # default impls of polymorphic methods which assume sequential layout of fields
+ # (like Struct or CaseOrBitcaseType)
+ def check_implicit_fixed_size_part_aligns(self):
+ # find places where the implementation of the C-binding would
+ # create code that makes the compiler add implicit alignment.
+ # make these places explicit, so we have
+ # consistent behaviour for all bindings
+ size = 0
+ for field in self.fields:
+ if not field.wire:
+ continue
+ if not field.type.fixed_size():
+ # end of fixed-size part
+ break
+ required_field_align = field.type.required_start_align
+ if required_field_align is None:
+ raise Exception(
+ "field \"%s\" in \"%s\" has not required_start_align"
+ % (field.field_name, self.name)
+ )
+ mis_align = (size + required_field_align.offset) % required_field_align.align
+ if mis_align != 0:
+ # implicit align pad is required
+ padsize = required_field_align.align - mis_align
+ raise Exception(
+ "C-compiler would insert implicit alignpad of size %d before field \"%s\" in \"%s\""
+ % (padsize, field.field_name, self.name)
+ )
+
+ def unchecked_get_alignment_after(self, start_align, callstack, log):
+ # default impl assumes sequential layout of fields
+ # (like Struct or CaseOrBitcaseType)
+ my_align = start_align
+ if my_align is None:
+ return None
+
+ for field in self.fields:
+ if not field.wire:
+ continue
+ my_callstack = callstack[:]
+ my_callstack.extend([self, field])
+
+ prev_align = my_align
+ my_align = field.type.get_alignment_after(my_align, my_callstack, log)
+ if my_align is None:
+ if log is not None:
+ log.fail(prev_align, field.field_name, self, my_callstack,
+ "alignment is incompatible with this field")
+ return None
+ else:
+ if log is not None:
+ log.ok(prev_align, field.field_name, self, my_callstack, my_align)
+
+ if log is not None:
+ my_callstack = callstack[:]
+ my_callstack.append(self)
+ log.ok(start_align, "", self, my_callstack, my_align)
+ return my_align
+
+
class SwitchType(ComplexType):
'''
Derived class which represents a List of Items.
Public fields added:
bitcases is an array of Bitcase objects describing the list items
'''
@@ -435,14 +777,15 @@ class SwitchType(ComplexType):
self.fields[idx] = new_field
inserted = True
break
if False == inserted:
self.fields.append(new_field)
self.calc_size() # Figure out how big we are
+ self.calc_or_check_required_start_align()
self.resolved = True
def make_member_of(self, module, complex_type, field_type, field_name, visible, wire, auto, enum=None):
if not self.fixed_size():
# We need a length field.
# Ask our Expression object for it's name, type, and whether it's on the wire.
lenfid = self.expr.lenfield_type
@@ -475,14 +818,131 @@ class SwitchType(ComplexType):
return False
# for m in self.fields:
# if not m.type.fixed_size():
# return False
# return True
+
+ def check_implicit_fixed_size_part_aligns(self):
+ # this is done for the CaseType or BitCaseType
+ return
+
+ def unchecked_get_alignment_after(self, start_align, callstack, log):
+ # we assume that BitCases can appear in any combination,
+ # and that at most one Case can appear
+ # (assuming that Cases are mutually exclusive)
+
+ # get all Cases (we assume that at least one case is selected if there are cases)
+ case_fields = []
+ for field in self.bitcases:
+ if field.type.is_case:
+ case_fields.append(field)
+
+ if not case_fields:
+ # there are no case-fields -> check without case-fields
+ case_fields = [None]
+
+ my_callstack = callstack[:]
+ my_callstack.append(self)
+ #
+ total_align = None
+ first = True
+ for case_field in case_fields:
+ my2_callstack = my_callstack[:]
+ if case_field is not None:
+ my2_callstack.append(case_field)
+
+ case_align = self.get_align_for_selected_case_field(
+ case_field, start_align, my2_callstack, log)
+
+
+ if case_align is None:
+ if log is not None:
+ if case_field is None:
+ log.fail(start_align, "", self, my2_callstack,
+ "alignment without cases (only bitcases) failed")
+ else:
+ log.fail(start_align, "", self, my2_callstack + [case_field],
+ "alignment for selected case %s failed"
+ % case_field.field_name)
+ return None
+ if first:
+ total_align = case_align
+ else:
+ total_align = total_align.combine_with(case_align)
+
+ if log is not None:
+ if case_field is None:
+ log.ok(
+ start_align,
+ "without cases (only arbitrary bitcases)",
+ self, my2_callstack, case_align)
+ else:
+ log.ok(
+ start_align,
+ "case %s and arbitrary bitcases" % case_field.field_name,
+ self, my2_callstack, case_align)
+
+
+ if log is not None:
+ log.ok(start_align, "", self, my_callstack, total_align)
+ return total_align
+
+ # aux function for unchecked_get_alignment_after
+ def get_align_for_selected_case_field(self, case_field, start_align, callstack, log):
+ if verbose_align_log:
+ print "get_align_for_selected_case_field: %s, case_field = %s" % (str(self), str(case_field))
+ total_align = start_align
+ for field in self.bitcases:
+ my_callstack = callstack[:]
+ my_callstack.append(field)
+
+ if not field.wire:
+ continue
+ if field is case_field:
+ # assume that this field is active -> no combine_with to emulate optional
+ after_field_align = field.type.get_alignment_after(total_align, my_callstack, log)
+
+ if log is not None:
+ if after_field_align is None:
+ log.fail(total_align, field.field_name, field.type, my_callstack,
+ "invalid aligment for this case branch")
+ else:
+ log.ok(total_align, field.field_name, field.type, my_callstack,
+ after_field_align)
+
+ total_align = after_field_align
+ elif field.type.is_bitcase:
+ after_field_align = field.type.get_alignment_after(total_align, my_callstack, log)
+ # we assume that this field is optional, therefore combine
+ # alignment after the field with the alignment before the field.
+ if after_field_align is None:
+ if log is not None:
+ log.fail(total_align, field.field_name, field.type, my_callstack,
+ "invalid aligment for this bitcase branch")
+ total_align = None
+ else:
+ if log is not None:
+ log.ok(total_align, field.field_name, field.type, my_callstack,
+ after_field_align)
+
+ # combine with the align before the field because
+ # the field is optional
+ total_align = total_align.combine_with(after_field_align)
+ else:
+ # ignore other fields as they are irrelevant for alignment
+ continue
+
+ if total_align is None:
+ break
+
+ return total_align
+
+
class Struct(ComplexType):
'''
Derived class representing a struct data type.
'''
out = __main__.output['struct']
@@ -493,28 +953,86 @@ class Union(ComplexType):
def __init__(self, name, elt):
ComplexType.__init__(self, name, elt)
self.is_union = True
out = __main__.output['union']
+ def calc_size(self):
+ self.size = 0
+ for m in self.fields:
+ if not m.wire:
+ continue
+ if m.type.fixed_size():
+ self.size = max(self.size, m.type.get_total_size())
+ else:
+ self.size = None
+ break
+
+
+ def check_implicit_fixed_size_part_aligns(self):
+ # a union does not have implicit aligns because all fields start
+ # at the start of the union
+ return
+
+
+ def unchecked_get_alignment_after(self, start_align, callstack, log):
+ my_callstack = callstack[:]
+ my_callstack.append(self)
+
+ after_align = None
+ if self.fixed_size():
+
+ #check proper alignment for all members
+ start_align_ok = all(
+ [field.type.is_acceptable_start_align(start_align, my_callstack + [field], log)
+ for field in self.fields])
+
+ if start_align_ok:
+ #compute the after align from the start_align
+ after_align = start_align.align_after_fixed_size(self.get_total_size())
+ else:
+ after_align = None
+
+ if log is not None and after_align is not None:
+ log.ok(start_align, "fixed sized union", self, my_callstack, after_align)
+
+ else:
+ if start_align is None:
+ if log is not None:
+ log.fail(start_align, "", self, my_callstack,
+ "missing start_align for union")
+ return None
+
+ after_align = reduce(
+ lambda x, y: None if x is None or y is None else x.combine_with(y),
+ [field.type.get_alignment_after(start_align, my_callstack + [field], log)
+ for field in self.fields])
+
+ if log is not None and after_align is not None:
+ log.ok(start_align, "var sized union", self, my_callstack, after_align)
+
+
+ if after_align is None and log is not None:
+ log.fail(start_align, "", self, my_callstack, "start_align is not ok for all members")
+
+ return after_align
+
class CaseOrBitcaseType(ComplexType):
'''
Derived class representing a case or bitcase.
'''
def __init__(self, index, name, elt, *parent):
elts = list(elt)
self.expr = []
- fields = []
- for elt in elts:
- if elt.tag == 'enumref':
- self.expr.append(Expression(elt, self))
- else:
- fields.append(elt)
- ComplexType.__init__(self, name, fields)
+ for sub_elt in elts:
+ if sub_elt.tag == 'enumref':
+ self.expr.append(Expression(sub_elt, self))
+ elt.remove(sub_elt)
+ ComplexType.__init__(self, name, elt)
self.has_name = True
self.index = 1
self.lenfield_parent = list(parent) + [self]
self.parents = list(parent)
self.is_case_or_bitcase = True
def make_member_of(self, module, switch_type, field_type, field_name, visible, wire, auto, enum=None):
@@ -541,14 +1059,17 @@ class CaseOrBitcaseType(ComplexType):
for e in self.expr:
e.resolve(module, self.parents+[self])
# Resolve the bitcase expression
ComplexType.resolve(self, module)
+ #calculate alignment
+ self.calc_or_check_required_start_align()
+
class BitcaseType(CaseOrBitcaseType):
'''
Derived class representing a bitcase.
'''
def __init__(self, index, name, elt, *parent):
CaseOrBitcaseType.__init__(self, index, name, elt, *parent)
@@ -567,14 +1088,16 @@ class Reply(ComplexType):
'''
Derived class representing a reply. Only found as a field of Request.
'''
def __init__(self, name, elt):
ComplexType.__init__(self, name, elt)
self.is_reply = True
self.doc = None
+ if self.required_start_align is None:
+ self.required_start_align = Alignment(4,0)
for child in list(elt):
if child.tag == 'doc':
self.doc = Doc(name, child)
def resolve(self, module):
if self.resolved:
@@ -598,14 +1121,16 @@ class Request(ComplexType):
opcode contains the request number.
'''
def __init__(self, name, elt):
ComplexType.__init__(self, name, elt)
self.reply = None
self.doc = None
self.opcode = elt.get('opcode')
+ if self.required_start_align is None:
+ self.required_start_align = Alignment(4,0)
for child in list(elt):
if child.tag == 'reply':
self.reply = Reply(name, child)
if child.tag == 'doc':
self.doc = Doc(name, child)
@@ -635,14 +1160,18 @@ class Event(ComplexType):
Derived class representing an event data type.
Public fields added:
opcodes is a dictionary of name -> opcode number, for eventcopies.
'''
def __init__(self, name, elt):
ComplexType.__init__(self, name, elt)
+
+ if self.required_start_align is None:
+ self.required_start_align = Alignment(4,0)
+
self.opcodes = {}
self.has_seq = not bool(elt.get('no-sequence-number'))
self.is_ge_event = bool(elt.get('xge'))
self.doc = None
@@ -689,14 +1218,16 @@ class Error(ComplexType):
Public fields added:
opcodes is a dictionary of name -> opcode number, for errorcopies.
'''
def __init__(self, name, elt):
ComplexType.__init__(self, name, elt)
self.opcodes = {}
+ if self.required_start_align is None:
+ self.required_start_align = Alignment(4,0)
def add_opcode(self, opcode, name, main):
self.opcodes[name] = opcode
if main:
self.name = name
def resolve(self, module):
--
2.1.4
More information about the Xcb
mailing list