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