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