nmigen_soc/memory.py

   1 import bisect
   2
   3
   4 __all__ = ["MemoryMap"]
   5
   6
   7 class _RangeMap:
   8     """Range map.
   9
  10     A range map is a mapping from non-overlapping ranges to arbitrary values.
  11     """
  12     def __init__(self):
  13         self._keys   = []
  14         self._values = dict()
  15         self._starts = []
  16         self._stops  = []
  17
  18     def insert(self, key, value):
  19         assert isinstance(key, range)
  20         assert not self.overlaps(key)
  21
  22         start_idx = bisect.bisect_right(self._starts, key.start)
  23         stop_idx  = bisect.bisect_left(self._stops, key.stop)
  24         assert start_idx == stop_idx
  25
  26         self._starts.insert(start_idx, key.start)
  27         self._stops.insert(stop_idx, key.stop)
  28         self._keys.insert(start_idx, key)
  29         self._values[key] = value
  30
  31     def get(self, point):
  32         point_idx = bisect.bisect_right(self._stops, point)
  33         if point_idx < len(self._keys):
  34             point_range = self._keys[point_idx]
  35             if point >= point_range.start and point < point_range.stop:
  36                 return self._values[point_range]
  37
  38     def overlaps(self, key):
  39         start_idx = bisect.bisect_right(self._stops, key.start)
  40         stop_idx  = bisect.bisect_left(self._starts, key.stop)
  41         return [self._values[key] for key in self._keys[start_idx:stop_idx]]
  42
  43     def items(self):
  44         for key in self._keys:
  45             yield key, self._values[key]
  46
  47
  48 class MemoryMap:
  49     """Memory map.
  50
  51     A memory map is a hierarchical description of an address space, describing the structure of
  52     address decoders of peripherals as well as bus bridges. It is built by adding resources
  53     (range allocations for registers, memory, etc) and windows (range allocations for bus bridges),
  54     and can be queried later to determine the address of any given resource from a specific
  55     vantage point in the design.
  56
  57     Address assignment
  58     ------------------
  59
  60     To simplify address assignment, each memory map has an implicit next address, starting at 0.
  61     If a resource or a window is added without specifying an address explicitly, the implicit next
  62     address is used. In any case, the implicit next address is set to the address immediately
  63     following the newly added resource or window.
  64
  65     Parameters
  66     ----------
  67     addr_width : int
  68         Address width.
  69     data_width : int
  70         Data width.
  71     alignment : int
  72         Range alignment. Each added resource and window will be placed at an address that is
  73         a multiple of ``2 ** alignment``, and its size will be rounded up to be a multiple of
  74         ``2 ** alignment``.
  75     """
  76     def __init__(self, *, addr_width, data_width, alignment=0):
  77         if not isinstance(addr_width, int) or addr_width <= 0:
  78             raise ValueError("Address width must be a positive integer, not {!r}"
  79                              .format(addr_width))
  80         if not isinstance(data_width, int) or data_width <= 0:
  81             raise ValueError("Data width must be a positive integer, not {!r}"
  82                              .format(data_width))
  83         if not isinstance(alignment, int) or alignment < 0:
  84             raise ValueError("Alignment must be a non-negative integer, not {!r}"
  85                              .format(alignment))
  86
  87         self.addr_width = addr_width
  88         self.data_width = data_width
  89         self.alignment  = alignment
  90
  91         self._ranges    = _RangeMap()
  92         self._resources = dict()
  93         self._windows   = dict()
  94
  95         self._next_addr = 0
  96
  97     @staticmethod
  98     def _align_up(value, alignment):
  99         if value % (1 << alignment) != 0:
 100             value += (1 << alignment) - (value % (1 << alignment))
 101         return value
 102
 103     def align_to(self, alignment):
 104         """Align the implicit next address.
 105
 106         Arguments
 107         ---------
 108         alignment : int
 109             Address alignment. The start of the implicit next address will be a multiple of
 110             ``2 ** max(alignment, self.alignment)``.
 111
 112         Return value
 113         ------------
 114         Implicit next address.
 115         """
 116         if not isinstance(alignment, int) or alignment < 0:
 117             raise ValueError("Alignment must be a non-negative integer, not {!r}"
 118                              .format(alignment))
 119         self._next_addr = self._align_up(self._next_addr, max(alignment, self.alignment))
 120         return self._next_addr
 121
 122     def _compute_addr_range(self, addr, size, step=1, *, alignment):
 123         if addr is not None:
 124             if not isinstance(addr, int) or addr < 0:
 125                 raise ValueError("Address must be a non-negative integer, not {!r}"
 126                                  .format(addr))
 127             if addr % (1 << self.alignment) != 0:
 128                 raise ValueError("Explicitly specified address {:#x} must be a multiple of "
 129                                  "{:#x} bytes"
 130                                  .format(addr, 1 << alignment))
 131         else:
 132             addr = self._align_up(self._next_addr, alignment)
 133
 134         if not isinstance(size, int) or size < 0:
 135             raise ValueError("Size must be a non-negative integer, not {!r}"
 136                              .format(size))
 137         size = self._align_up(size, alignment)
 138
 139         if addr > (1 << self.addr_width) or addr + size > (1 << self.addr_width):
 140             raise ValueError("Address range {:#x}..{:#x} out of bounds for memory map spanning "
 141                              "range {:#x}..{:#x} ({} address bits)"
 142                              .format(addr, addr + size, 0, 1 << self.addr_width, self.addr_width))
 143
 144         addr_range = range(addr, addr + size, step)
 145         overlaps = self._ranges.overlaps(addr_range)
 146         if overlaps:
 147             overlap_descrs = []
 148             for overlap in overlaps:
 149                 if overlap in self._resources:
 150                     resource_range = self._resources[overlap]
 151                     overlap_descrs.append("resource {!r} at {:#x}..{:#x}"
 152                         .format(overlap, resource_range.start, resource_range.stop))
 153                 if overlap in self._windows:
 154                     overlap_descrs.append("window {!r} at {:#x}..{:#x}"
 155                         .format(overlap, resource_range.start, resource_range.stop))
 156             raise ValueError("Address range {:#x}..{:#x} overlaps with {}"
 157                              .format(addr, addr + size, ", ".join(overlap_descrs)))
 158
 159         return addr_range
 160
 161     def add_resource(self, resource, *, size, addr=None, alignment=None):
 162         """Add a resource.
 163
 164         A resource is any device on the bus that is a destination for bus transactions, e.g.
 165         a register or a memory block.
 166
 167         Arguments
 168         ---------
 169         resource : object
 170             Arbitrary object representing a resource.
 171         addr : int or None
 172             Address of the resource. If ``None``, the implicit next address will be used.
 173             Otherwise, the exact specified address (which must be a multiple of
 174             ``2 ** max(alignment, self.alignment)``) will be used.
 175         size : int
 176             Size of the resource, in minimal addressable units. Rounded up to a multiple of
 177             ``2 ** max(alignment, self.alignment)``.
 178         alignment : int or None
 179             Alignment of the resource. If not specified, the memory map alignment is used.
 180
 181         Return value
 182         ------------
 183         A tuple ``(start, end)`` describing the address range assigned to the resource.
 184
 185         Exceptions
 186         ----------
 187         Raises :exn:`ValueError` if the requested address and size, after alignment, would overlap
 188         with any resources or windows that have already been added, or would be out of bounds.
 189         """
 190         if resource in self._resources:
 191             addr_range = self._resources[resource]
 192             raise ValueError("Resource {!r} is already added at address range {:#x}..{:#x}"
 193                              .format(resource, addr_range.start, addr_range.stop))
 194
 195         if alignment is not None:
 196             if not isinstance(alignment, int) or alignment < 0:
 197                 raise ValueError("Alignment must be a non-negative integer, not {!r}"
 198                                  .format(alignment))
 199             alignment = max(alignment, self.alignment)
 200         else:
 201             alignment = self.alignment
 202
 203         addr_range = self._compute_addr_range(addr, size, alignment=alignment)
 204         self._ranges.insert(addr_range, resource)
 205         self._resources[resource] = addr_range
 206         self._next_addr = addr_range.stop
 207         return addr_range.start, addr_range.stop
 208
 209     def resources(self):
 210         """Iterate local resources and their address ranges.
 211
 212         Non-recursively iterate resources in ascending order of their address.
 213
 214         Yield values
 215         ------------
 216         A tuple ``resource, (start, end)`` describing the address range assigned to the resource.
 217         """
 218         for resource, resource_range in self._resources.items():
 219             yield resource, (resource_range.start, resource_range.stop)
 220
 221     def add_window(self, window, *, addr=None, sparse=None):
 222         """Add a window.
 223
 224         A window is a device on a bus that provides access to a different bus, i.e. a bus bridge.
 225         It performs address translation, such that the devices on a subordinate bus have different
 226         addresses; the memory map reflects this address translation when resources are looked up
 227         through the window.
 228
 229         Sparse addressing
 230         -----------------
 231
 232         If a narrow bus is bridged to a wide bus, the bridge can perform *sparse* or *dense*
 233         address translation. In the sparse case, each transaction on the wide bus results in
 234         one transaction on the narrow bus; high data bits on the wide bus are ignored, and any
 235         contiguous resource on the narrow bus becomes discontiguous on the wide bus. In the dense
 236         case, each transaction on the wide bus results in several transactions on the narrow bus,
 237         and any contiguous resource on the narrow bus stays contiguous on the wide bus.
 238
 239         Arguments
 240         ---------
 241         window : :class:`MemoryMap`
 242             A memory map describing the layout of the window.
 243         addr : int or None
 244             Address of the window. If ``None``, the implicit next address will be used after
 245             aligning it to ``2 ** window.addr_width``. Otherwise, the exact specified address
 246             (which must be a multiple of ``2 ** window.addr_width``) will be used.
 247         sparse : bool or None
 248             Address translation type. Ignored if the datapath widths of both memory maps are
 249             equal; must be specified otherwise.
 250
 251         Return value
 252         ------------
 253         A tuple ``(start, end, ratio)`` describing the address range assigned to the window.
 254         When bridging buses of unequal data width, ``ratio`` is the amount of contiguous addresses
 255         on the narrower bus that are accessed for each transaction on the wider bus. Otherwise,
 256         it is always 1.
 257
 258         Exceptions
 259         ----------
 260         Raises :exn:`ValueError` if the requested address and size, after alignment, would overlap
 261         with any resources or windows that have already been added, or would be out of bounds;
 262         if the added memory map has wider datapath than this memory map; if dense address
 263         translation is used and the datapath width of this memory map is not an integer multiple
 264         of the datapath width of the added memory map.
 265         """
 266         if not isinstance(window, MemoryMap):
 267             raise TypeError("Window must be a MemoryMap, not {!r}"
 268                             .format(window))
 269         if window in self._windows:
 270             addr_range = self._windows[window]
 271             raise ValueError("Window {!r} is already added at address range {:#x}..{:#x}"
 272                              .format(window, addr_range.start, addr_range.stop))
 273
 274         if window.data_width > self.data_width:
 275             raise ValueError("Window has data width {}, and cannot be added to a memory map "
 276                              "with data width {}"
 277                              .format(window.data_width, self.data_width))
 278         if window.data_width != self.data_width:
 279             if sparse is None:
 280                 raise ValueError("Address translation mode must be explicitly specified "
 281                                  "when adding a window with data width {} to a memory map "
 282                                  "with data width {}"
 283                                  .format(window.data_width, self.data_width))
 284             if not sparse and self.data_width % window.data_width != 0:
 285                 raise ValueError("Dense addressing cannot be used because the memory map "
 286                                  "data width {} is not an integer multiple of window "
 287                                  "data width {}"
 288                                  .format(self.data_width, window.data_width))
 289
 290         if not sparse:
 291             ratio = self.data_width // window.data_width
 292         else:
 293             ratio = 1
 294         size = (1 << window.addr_width) // ratio
 295         # For resources, the alignment argument of add_resource() affects both address and size
 296         # of the resource; aligning only the address should be done using align_to(). For windows,
 297         # changing the size (beyond the edge case of the window size being smaller than alignment
 298         # of the bus) is unlikely to be useful, so there is no alignment argument. The address of
 299         # a window can still be aligned using align_to().
 300         alignment = max(self.alignment, window.addr_width // ratio)
 301
 302         addr_range = self._compute_addr_range(addr, size, ratio, alignment=alignment)
 303         self._ranges.insert(addr_range, window)
 304         self._windows[window] = addr_range
 305         self._next_addr = addr_range.stop
 306         return addr_range.start, addr_range.stop, addr_range.step
 307
 308     def windows(self):
 309         """Iterate local windows and their address ranges.
 310
 311         Non-recursively iterate windows in ascending order of their address.
 312
 313         Yield values
 314         ------------
 315         A tuple ``window, (start, end, ratio)`` describing the address range assigned to
 316         the window. When bridging buses of unequal data width, ``ratio`` is the amount of
 317         contiguous addresses on the narrower bus that are accessed for each transaction on
 318         the wider bus. Otherwise, it is always 1.
 319         """
 320         for window, window_range in self._windows.items():
 321             yield window, (window_range.start, window_range.stop, window_range.step)
 322
 323     @staticmethod
 324     def _translate(start, end, width, window, window_range):
 325         assert (end - start) % window_range.step == 0
 326         # Accessing a resource through a dense and then a sparse window results in very strange
 327         # layouts that cannot be easily represented, so reject those.
 328         assert window_range.step == 1 or width == window.data_width
 329         size   = (end - start) // window_range.step
 330         start += window_range.start
 331         width *= window_range.step
 332         return start, start + size, width
 333
 334     def all_resources(self):
 335         """Iterate all resources and their address ranges.
 336
 337         Recursively iterate all resources in ascending order of their address, performing address
 338         translation for resources that are located behind a window.
 339
 340         Yield values
 341         ------------
 342         A tuple ``resource, (start, end, width)`` describing the address range assigned to
 343         the resource. ``width`` is the amount of data bits accessed at each address, which may be
 344         equal to ``self.data_width``, or less if the resource is located behind a window that
 345         uses sparse addressing.
 346         """
 347         for addr_range, assignment in self._ranges.items():
 348             if assignment in self._resources:
 349                 yield assignment, (addr_range.start, addr_range.stop, self.data_width)
 350             elif assignment in self._windows:
 351                 for sub_resource, sub_descr in assignment.all_resources():
 352                     yield sub_resource, self._translate(*sub_descr, assignment, addr_range)
 353             else:
 354                 assert False
 355
 356     def find_resource(self, resource):
 357         """Find address range corresponding to a resource.
 358
 359         Recursively find the address range of a resource, performing address translation for
 360         resources that are located behind a window.
 361
 362         Arguments
 363         ---------
 364         resource
 365             Resource previously added to this memory map or any windows.
 366
 367         Return value
 368         ------------
 369         A tuple ``(start, end, width)`` describing the address range assigned to the resource.
 370         ``width`` is the amount of data bits accessed at each address, which may be equal to
 371         ``self.data_width``, or less if the resource is located behind a window that uses sparse
 372         addressing.
 373
 374         Exceptions
 375         ----------
 376         Raises :exn:`KeyError` if the resource is not found.
 377         """
 378         if resource in self._resources:
 379             resource_range = self._resources[resource]
 380             return resource_range.start, resource_range.stop, self.data_width
 381
 382         for window, window_range in self._windows.items():
 383             try:
 384                 return self._translate(*window.find_resource(resource), window, window_range)
 385             except KeyError:
 386                 pass
 387
 388         raise KeyError(resource)
 389
 390     def decode_address(self, address):
 391         """Decode an address to a resource.
 392
 393         Arguments
 394         ---------
 395         address : int
 396             Address of interest.
 397
 398         Return value
 399         ------------
 400         A resource mapped to the provided address, or ``None`` if there is no such resource.
 401         """
 402         assignment = self._ranges.get(address)
 403         if assignment is None:
 404             return
 405
 406         if assignment in self._resources:
 407             return assignment
 408         elif assignment in self._windows:
 409             addr_range = self._windows[assignment]
 410             return assignment.decode_address((address - addr_range.start) // addr_range.step)
 411         else:
 412             assert False