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