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
 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         alignment = max(self.alignment, window.addr_width // ratio)
 296
 297         addr_range = self._compute_addr_range(addr, size, ratio, alignment=alignment)
 298         self._ranges.insert(addr_range, window)
 299         self._windows[window] = addr_range
 300         self._next_addr = addr_range.stop
 301         return addr_range.start, addr_range.stop, addr_range.step
 302
 303     def windows(self):
 304         """Iterate local windows and their address ranges.
 305
 306         Non-recursively iterate windows in ascending order of their address.
 307
 308         Yield values
 309         ------------
 310         A tuple ``window, (start, end, ratio)`` describing the address range assigned to
 311         the window. When bridging buses of unequal data width, ``ratio`` is the amount of
 312         contiguous addresses on the narrower bus that are accessed for each transaction on
 313         the wider bus. Otherwise, it is always 1.
 314         """
 315         for window, window_range in self._windows.items():
 316             yield window, (window_range.start, window_range.stop, window_range.step)
 317
 318     @staticmethod
 319     def _translate(start, end, width, window, window_range):
 320         assert (end - start) % window_range.step == 0
 321         # Accessing a resource through a dense and then a sparse window results in very strange
 322         # layouts that cannot be easily represented, so reject those.
 323         assert window_range.step == 1 or width == window.data_width
 324         size   = (end - start) // window_range.step
 325         start += window_range.start
 326         width *= window_range.step
 327         return start, start + size, width
 328
 329     def all_resources(self):
 330         """Iterate all resources and their address ranges.
 331
 332         Recursively iterate all resources in ascending order of their address, performing address
 333         translation for resources that are located behind a window.
 334
 335         Yield values
 336         ------------
 337         A tuple ``resource, (start, end, width)`` describing the address range assigned to
 338         the resource. ``width`` is the amount of data bits accessed at each address, which may be
 339         equal to ``self.data_width``, or less if the resource is located behind a window that
 340         uses sparse addressing.
 341         """
 342         for addr_range, assignment in self._ranges.items():
 343             if assignment in self._resources:
 344                 yield assignment, (addr_range.start, addr_range.stop, self.data_width)
 345             elif assignment in self._windows:
 346                 for sub_resource, sub_descr in assignment.all_resources():
 347                     yield sub_resource, self._translate(*sub_descr, assignment, addr_range)
 348             else:
 349                 assert False
 350
 351     def find_resource(self, resource):
 352         """Find address range corresponding to a resource.
 353
 354         Recursively find the address range of a resource, performing address translation for
 355         resources that are located behind a window.
 356
 357         Arguments
 358         ---------
 359         resource
 360             Resource previously added to this memory map or any windows.
 361
 362         Return value
 363         ------------
 364         A tuple ``(start, end, width)`` describing the address range assigned to the resource.
 365         ``width`` is the amount of data bits accessed at each address, which may be equal to
 366         ``self.data_width``, or less if the resource is located behind a window that uses sparse
 367         addressing.
 368
 369         Exceptions
 370         ----------
 371         Raises :exn:`KeyError` if the resource is not found.
 372         """
 373         if resource in self._resources:
 374             resource_range = self._resources[resource]
 375             return resource_range.start, resource_range.stop, self.data_width
 376
 377         for window, window_range in self._windows.items():
 378             try:
 379                 return self._translate(*window.find_resource(resource), window, window_range)
 380             except KeyError:
 381                 pass
 382
 383         raise KeyError(resource)
 384
 385     def decode_address(self, address):
 386         """Decode an address to a resource.
 387
 388         Arguments
 389         ---------
 390         address : int
 391             Address of interest.
 392
 393         Return value
 394         ------------
 395         A resource mapped to the provided address, or ``None`` if there is no such resource.
 396         """
 397         assignment = self._ranges.get(address)
 398         if assignment is None:
 399             return
 400
 401         if assignment in self._resources:
 402             return assignment
 403         elif assignment in self._windows:
 404             addr_range = self._windows[assignment]
 405             return assignment.decode_address((address - addr_range.start) // addr_range.step)
 406         else:
 407             assert False