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() affects both address and size
 333         # of the resource; aligning only the address should be done using align_to(). For windows,
 334         # changing the size (beyond the edge case of the window size being smaller than alignment
 335         # of the bus) is unlikely to be useful, so there is no alignment argument. The address of
 336         # a window can still be aligned using align_to().
 337         alignment = max(self.alignment, window.addr_width // ratio)
 338
 339         addr_range = self._compute_addr_range(
 340             addr, size, ratio, alignment=alignment)
 341         self._ranges.insert(addr_range, window)
 342         self._windows[window] = addr_range
 343         self._next_addr = addr_range.stop
 344         return addr_range.start, addr_range.stop, addr_range.step
 345
 346     def windows(self):
 347         """Iterate local windows and their address ranges.
 348
 349         Non-recursively iterate windows in ascending order of their address.
 350
 351         Yield values
 352         ------------
 353         A tuple ``window, (start, end, ratio)`` describing the address
 354         range assigned to the window. When bridging buses of unequal
 355         data width, ``ratio`` is the amount of contiguous addresses on
 356         the narrower bus that are accessed for each transaction on the
 357         wider bus. Otherwise, it is always 1.
 358         """
 359         for window, window_range in self._windows.items():
 360             yield window, (window_range.start, window_range.stop,
 361                            window_range.step)
 362
 363     def window_patterns(self):
 364         """Iterate local windows and patterns that match their address ranges.
 365
 366         Non-recursively iterate windows in ascending order of their address.
 367
 368         Yield values
 369         ------------
 370         A tuple ``window, (pattern, ratio)`` describing the address range
 371         assigned to the window.  ``pattern`` is a ``self.addr_width``
 372         wide pattern that may be used in ``Case`` or ``match`` to
 373         determine if an address signal is within the address range of
 374         ``window``. When bridging buses of unequal data width, ``ratio``
 375         is the amount of contiguous addresses on the narrower bus that
 376         are accessed for each transaction on the wider bus. Otherwise,
 377         it is always 1.
 378         """
 379         for window, window_range in self._windows.items():
 380             pattern = "{:0{}b}{}".format((window_range.start >>
 381                                          window.addr_width),
 382                                          self.addr_width - window.addr_width,
 383                                          "-" * window.addr_width)
 384             yield window, (pattern, window_range.step)
 385
 386     @staticmethod
 387     def _translate(start, end, width, window, window_range):
 388         assert (end - start) % window_range.step == 0
 389         # Accessing a resource through a dense and then a sparse window results in very strange
 390         # layouts that cannot be easily represented, so reject those.
 391         assert window_range.step == 1 or width == window.data_width
 392         size = (end - start) // window_range.step
 393         start += window_range.start
 394         width *= window_range.step
 395         return start, start + size, width
 396
 397     def all_resources(self):
 398         """Iterate all resources and their address ranges.
 399
 400         Recursively iterate all resources in ascending order of their
 401         address, performing address translation for resources that are
 402         located behind a window.
 403
 404         Yield values ------------ A tuple ``resource, (start,
 405         end, width)`` describing the address range assigned to the
 406         resource. ``width`` is the amount of data bits accessed at each
 407         address, which may be equal to ``self.data_width``, or less if the
 408         resource is located behind a window that uses sparse addressing.
 409         """
 410         for addr_range, assignment in self._ranges.items():
 411             if assignment in self._resources:
 412                 yield assignment, (addr_range.start, addr_range.stop,
 413                                     self.data_width)
 414             elif assignment in self._windows:
 415                 for sub_resource, sub_descr in assignment.all_resources():
 416                     yield sub_resource, self._translate(*sub_descr,
 417                                                 assignment,
 418                                                 addr_range)
 419             else:
 420                 assert False  # :nocov:
 421
 422     def find_resource(self, resource):
 423         """Find address range corresponding to a resource.
 424
 425         Recursively find the address range of a resource, performing
 426         address translation for resources that are located behind
 427         a window.
 428
 429         Arguments
 430         ---------
 431         resource
 432             Resource previously added to this memory map or any windows.
 433
 434         Return value
 435         ------------
 436         A tuple ``(start, end, width)`` describing the address
 437         range assigned to the resource.  ``width`` is the amount of
 438         data bits accessed at each address, which may be equal to
 439         ``self.data_width``, or less if the resource is located behind
 440         a window that uses sparse addressing.
 441
 442         Exceptions
 443         ----------
 444         Raises :exn:`KeyError` if the resource is not found.
 445         """
 446         if resource in self._resources:
 447             resource_range = self._resources[resource]
 448             return resource_range.start, resource_range.stop, self.data_width
 449
 450         for window, window_range in self._windows.items():
 451             try:
 452                 return self._translate(*window.find_resource(resource),
 453                                                 window,
 454                                                 window_range)
 455             except KeyError:
 456                 pass
 457
 458         raise KeyError(resource)
 459
 460     def decode_address(self, address):
 461         """Decode an address to a resource.
 462
 463         Arguments
 464         ---------
 465         address : int
 466             Address of interest.
 467
 468         Return value
 469         ------------
 470         A resource mapped to the provided address, or ``None`` if there
 471         is no such resource.
 472         """
 473         assignment = self._ranges.get(address)
 474         if assignment is None:
 475             return
 476
 477         if assignment in self._resources:
 478             return assignment
 479         elif assignment in self._windows:
 480             addr_range = self._windows[assignment]
 481             return assignment.decode_address(
 482                 (address - addr_range.start) // addr_range.step)
 483         else:
 484             assert False  # :nocov: