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                     window_range = self._windows[overlap]
 155                     overlap_descrs.append("window {!r} at {:#x}..{:#x}"
 156                         .format(overlap, window_range.start, window_range.stop))
 157             raise ValueError("Address range {:#x}..{:#x} overlaps with {}"
 158                              .format(addr, addr + size, ", ".join(overlap_descrs)))
 159
 160         return addr_range
 161
 162     def add_resource(self, resource, *, size, addr=None, alignment=None):
 163         """Add a resource.
 164
 165         A resource is any device on the bus that is a destination for bus transactions, e.g.
 166         a register or a memory block.
 167
 168         Arguments
 169         ---------
 170         resource : object
 171             Arbitrary object representing a resource.
 172         addr : int or None
 173             Address of the resource. If ``None``, the implicit next address will be used.
 174             Otherwise, the exact specified address (which must be a multiple of
 175             ``2 ** max(alignment, self.alignment)``) will be used.
 176         size : int
 177             Size of the resource, in minimal addressable units. Rounded up to a multiple of
 178             ``2 ** max(alignment, self.alignment)``.
 179         alignment : int or None
 180             Alignment of the resource. If not specified, the memory map alignment is used.
 181
 182         Return value
 183         ------------
 184         A tuple ``(start, end)`` describing the address range assigned to the resource.
 185
 186         Exceptions
 187         ----------
 188         Raises :exn:`ValueError` if the requested address and size, after alignment, would overlap
 189         with any resources or windows that have already been added, or would be out of bounds.
 190         """
 191         if resource in self._resources:
 192             addr_range = self._resources[resource]
 193             raise ValueError("Resource {!r} is already added at address range {:#x}..{:#x}"
 194                              .format(resource, addr_range.start, addr_range.stop))
 195
 196         if alignment is not None:
 197             if not isinstance(alignment, int) or alignment < 0:
 198                 raise ValueError("Alignment must be a non-negative integer, not {!r}"
 199                                  .format(alignment))
 200             alignment = max(alignment, self.alignment)
 201         else:
 202             alignment = self.alignment
 203
 204         addr_range = self._compute_addr_range(addr, size, alignment=alignment)
 205         self._ranges.insert(addr_range, resource)
 206         self._resources[resource] = addr_range
 207         self._next_addr = addr_range.stop
 208         return addr_range.start, addr_range.stop
 209
 210     def resources(self):
 211         """Iterate local resources and their address ranges.
 212
 213         Non-recursively iterate resources in ascending order of their address.
 214
 215         Yield values
 216         ------------
 217         A tuple ``resource, (start, end)`` describing the address range assigned to the resource.
 218         """
 219         for resource, resource_range in self._resources.items():
 220             yield resource, (resource_range.start, resource_range.stop)
 221
 222     def add_window(self, window, *, addr=None, sparse=None):
 223         """Add a window.
 224
 225         A window is a device on a bus that provides access to a different bus, i.e. a bus bridge.
 226         It performs address translation, such that the devices on a subordinate bus have different
 227         addresses; the memory map reflects this address translation when resources are looked up
 228         through the window.
 229
 230         Sparse addressing
 231         -----------------
 232
 233         If a narrow bus is bridged to a wide bus, the bridge can perform *sparse* or *dense*
 234         address translation. In the sparse case, each transaction on the wide bus results in
 235         one transaction on the narrow bus; high data bits on the wide bus are ignored, and any
 236         contiguous resource on the narrow bus becomes discontiguous on the wide bus. In the dense
 237         case, each transaction on the wide bus results in several transactions on the narrow bus,
 238         and any contiguous resource on the narrow bus stays contiguous on the wide bus.
 239
 240         Arguments
 241         ---------
 242         window : :class:`MemoryMap`
 243             A memory map describing the layout of the window.
 244         addr : int or None
 245             Address of the window. If ``None``, the implicit next address will be used after
 246             aligning it to ``2 ** window.addr_width``. Otherwise, the exact specified address
 247             (which must be a multiple of ``2 ** window.addr_width``) will be used.
 248         sparse : bool or None
 249             Address translation type. Ignored if the datapath widths of both memory maps are
 250             equal; must be specified otherwise.
 251
 252         Return value
 253         ------------
 254         A tuple ``(start, end, ratio)`` describing the address range assigned to the window.
 255         When bridging buses of unequal data width, ``ratio`` is the amount of contiguous addresses
 256         on the narrower bus that are accessed for each transaction on the wider bus. Otherwise,
 257         it is always 1.
 258
 259         Exceptions
 260         ----------
 261         Raises :exn:`ValueError` if the requested address and size, after alignment, would overlap
 262         with any resources or windows that have already been added, or would be out of bounds;
 263         if the added memory map has wider datapath than this memory map; if dense address
 264         translation is used and the datapath width of this memory map is not an integer multiple
 265         of the datapath width of the added memory map.
 266         """
 267         if not isinstance(window, MemoryMap):
 268             raise TypeError("Window must be a MemoryMap, not {!r}"
 269                             .format(window))
 270         if window in self._windows:
 271             addr_range = self._windows[window]
 272             raise ValueError("Window {!r} is already added at address range {:#x}..{:#x}"
 273                              .format(window, addr_range.start, addr_range.stop))
 274
 275         if window.data_width > self.data_width:
 276             raise ValueError("Window has data width {}, and cannot be added to a memory map "
 277                              "with data width {}"
 278                              .format(window.data_width, self.data_width))
 279         if window.data_width != self.data_width:
 280             if sparse is None:
 281                 raise ValueError("Address translation mode must be explicitly specified "
 282                                  "when adding a window with data width {} to a memory map "
 283                                  "with data width {}"
 284                                  .format(window.data_width, self.data_width))
 285             if not sparse and self.data_width % window.data_width != 0:
 286                 raise ValueError("Dense addressing cannot be used because the memory map "
 287                                  "data width {} is not an integer multiple of window "
 288                                  "data width {}"
 289                                  .format(self.data_width, window.data_width))
 290
 291         if not sparse:
 292             ratio = self.data_width // window.data_width
 293         else:
 294             ratio = 1
 295         size = (1 << window.addr_width) // ratio
 296         # For resources, the alignment argument of add_resource() affects both address and size
 297         # of the resource; aligning only the address should be done using align_to(). For windows,
 298         # changing the size (beyond the edge case of the window size being smaller than alignment
 299         # of the bus) is unlikely to be useful, so there is no alignment argument. The address of
 300         # a window can still be aligned using align_to().
 301         alignment = max(self.alignment, window.addr_width // ratio)
 302
 303         addr_range = self._compute_addr_range(addr, size, ratio, alignment=alignment)
 304         self._ranges.insert(addr_range, window)
 305         self._windows[window] = addr_range
 306         self._next_addr = addr_range.stop
 307         return addr_range.start, addr_range.stop, addr_range.step
 308
 309     def windows(self):
 310         """Iterate local windows and their address ranges.
 311
 312         Non-recursively iterate windows in ascending order of their address.
 313
 314         Yield values
 315         ------------
 316         A tuple ``window, (start, end, ratio)`` describing the address range assigned to
 317         the window. When bridging buses of unequal data width, ``ratio`` is the amount of
 318         contiguous addresses on the narrower bus that are accessed for each transaction on
 319         the wider bus. Otherwise, it is always 1.
 320         """
 321         for window, window_range in self._windows.items():
 322             yield window, (window_range.start, window_range.stop, window_range.step)
 323
 324     def window_patterns(self):
 325         """Iterate local windows and patterns that match their address ranges.
 326
 327         Non-recursively iterate windows in ascending order of their address.
 328
 329         Yield values
 330         ------------
 331         A tuple ``window, pattern`` describing the address range assigned to the window.
 332         ``pattern`` is a ``self.addr_width`` wide pattern that may be used in ``Case`` or ``match``
 333         to determine if an address signal is within the address range of ``window``.
 334         """
 335         for window, window_range in self._windows.items():
 336             pattern = "{:0{}b}{}".format(window_range.start >> window.addr_width,
 337                                          self.addr_width - window.addr_width,
 338                                          "-" * window.addr_width)
 339             yield window, pattern
 340
 341     @staticmethod
 342     def _translate(start, end, width, window, window_range):
 343         assert (end - start) % window_range.step == 0
 344         # Accessing a resource through a dense and then a sparse window results in very strange
 345         # layouts that cannot be easily represented, so reject those.
 346         assert window_range.step == 1 or width == window.data_width
 347         size   = (end - start) // window_range.step
 348         start += window_range.start
 349         width *= window_range.step
 350         return start, start + size, width
 351
 352     def all_resources(self):
 353         """Iterate all resources and their address ranges.
 354
 355         Recursively iterate all resources in ascending order of their address, performing address
 356         translation for resources that are located behind a window.
 357
 358         Yield values
 359         ------------
 360         A tuple ``resource, (start, end, width)`` describing the address range assigned to
 361         the resource. ``width`` is the amount of data bits accessed at each address, which may be
 362         equal to ``self.data_width``, or less if the resource is located behind a window that
 363         uses sparse addressing.
 364         """
 365         for addr_range, assignment in self._ranges.items():
 366             if assignment in self._resources:
 367                 yield assignment, (addr_range.start, addr_range.stop, self.data_width)
 368             elif assignment in self._windows:
 369                 for sub_resource, sub_descr in assignment.all_resources():
 370                     yield sub_resource, self._translate(*sub_descr, assignment, addr_range)
 371             else:
 372                 assert False # :nocov:
 373
 374     def find_resource(self, resource):
 375         """Find address range corresponding to a resource.
 376
 377         Recursively find the address range of a resource, performing address translation for
 378         resources that are located behind a window.
 379
 380         Arguments
 381         ---------
 382         resource
 383             Resource previously added to this memory map or any windows.
 384
 385         Return value
 386         ------------
 387         A tuple ``(start, end, width)`` describing the address range assigned to the resource.
 388         ``width`` is the amount of data bits accessed at each address, which may be equal to
 389         ``self.data_width``, or less if the resource is located behind a window that uses sparse
 390         addressing.
 391
 392         Exceptions
 393         ----------
 394         Raises :exn:`KeyError` if the resource is not found.
 395         """
 396         if resource in self._resources:
 397             resource_range = self._resources[resource]
 398             return resource_range.start, resource_range.stop, self.data_width
 399
 400         for window, window_range in self._windows.items():
 401             try:
 402                 return self._translate(*window.find_resource(resource), window, window_range)
 403             except KeyError:
 404                 pass
 405
 406         raise KeyError(resource)
 407
 408     def decode_address(self, address):
 409         """Decode an address to a resource.
 410
 411         Arguments
 412         ---------
 413         address : int
 414             Address of interest.
 415
 416         Return value
 417         ------------
 418         A resource mapped to the provided address, or ``None`` if there is no such resource.
 419         """
 420         assignment = self._ranges.get(address)
 421         if assignment is None:
 422             return
 423
 424         if assignment in self._resources:
 425             return assignment
 426         elif assignment in self._windows:
 427             addr_range = self._windows[assignment]
 428             return assignment.decode_address((address - addr_range.start) // addr_range.step)
 429         else:
 430             assert False # :nocov: