4 __all__
= ["MemoryMap"]
10 A range map is a mapping from non-overlapping ranges to arbitrary values.
19 def insert(self
, key
, value
):
20 assert isinstance(key
, range)
21 assert not self
.overlaps(key
)
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
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
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
]
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
]]
45 for key
in self
._keys
:
46 yield key
, self
._values
[key
]
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.
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.
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``.
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
))
91 self
.addr_width
= addr_width
92 self
.data_width
= data_width
93 self
.alignment
= alignment
95 self
._ranges
= _RangeMap()
96 self
._resources
= dict()
97 self
._windows
= dict()
102 def _align_up(value
, alignment
):
103 if value
% (1 << alignment
) != 0:
104 value
+= (1 << alignment
) - (value
% (1 << alignment
))
107 def align_to(self
, alignment
):
108 """Align the implicit next address.
113 Address alignment. The start of the implicit next address
114 will be a multiple of ``2 ** max(alignment, self.alignment)``.
118 Implicit next address.
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
128 def _compute_addr_range(self
, addr
, size
, step
=1, *, alignment
):
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
))
138 addr
= self
._align
_up
(self
._next
_addr
, alignment
)
140 if not isinstance(size
, int) or size
< 0:
141 raise ValueError("Size must be a non-negative integer, not {!r}"
143 size
= self
._align
_up
(size
, alignment
)
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
))
152 addr_range
= range(addr
, addr
+ size
, step
)
153 overlaps
= self
._ranges
.overlaps(addr_range
)
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}"
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}"
169 raise ValueError("Address range {:#x}..{:#x} overlaps with {}"
172 ", ".join(overlap_descrs
)))
176 def add_resource(self
, resource
, *, size
, addr
=None, alignment
=None):
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.
185 Arbitrary object representing a resource.
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.
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
200 A tuple ``(start, end)`` describing the address range assigned
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.
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
,
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
)
222 alignment
= self
.alignment
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
231 """Iterate local resources and their address ranges.
233 Non-recursively iterate resources in ascending order of their address.
237 A tuple ``resource, (start, end)`` describing the address range
238 assigned to the resource.
240 for resource
, resource_range
in self
._resources
.items():
241 yield resource
, (resource_range
.start
, resource_range
.stop
)
243 def add_window(self
, window
, *, addr
=None, sparse
=None):
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.
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
267 window : :class:`MemoryMap`
268 A memory map describing the layout of the window.
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``)
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.
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.
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.
297 if not isinstance(window
, MemoryMap
):
298 raise TypeError("Window must be a MemoryMap, not {!r}"
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
))
306 if window
.data_width
> self
.data_width
:
307 raise ValueError("Window has data width {}, and cannot "
308 "be added to a memory map "
310 .format(window
.data_width
, self
.data_width
))
311 if window
.data_width
!= self
.data_width
:
313 raise ValueError("Address translation mode must be "
314 "explicitly specified "
315 "when adding a window with "
316 "data width {} to a memory map "
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 "
325 .format(self
.data_width
, window
.data_width
))
328 ratio
= self
.data_width
// window
.data_width
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
)
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
349 """Iterate local windows and their address ranges.
351 Non-recursively iterate windows in ascending order of their address.
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.
361 for window
, window_range
in self
._windows
.items():
362 yield window
, (window_range
.start
, window_range
.stop
,
365 def window_patterns(self
):
366 """Iterate local windows and patterns that match their address ranges.
368 Non-recursively iterate windows in ascending order of their address.
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,
381 for window
, window_range
in self
._windows
.items():
382 pattern
= "{:0{}b}{}".format((window_range
.start
>>
384 self
.addr_width
- window
.addr_width
,
385 "-" * window
.addr_width
)
386 yield window
, (pattern
, window_range
.step
)
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
400 def all_resources(self
):
401 """Iterate all resources and their address ranges.
403 Recursively iterate all resources in ascending order of their
404 address, performing address translation for resources that are
405 located behind a window.
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.
413 for addr_range
, assignment
in self
._ranges
.items():
414 if assignment
in self
._resources
:
415 yield assignment
, (addr_range
.start
, addr_range
.stop
,
417 elif assignment
in self
._windows
:
418 for sub_resource
, sub_descr
in assignment
.all_resources():
419 yield sub_resource
, self
._translate
(*sub_descr
,
423 assert False # :nocov:
425 def find_resource(self
, resource
):
426 """Find address range corresponding to a resource.
428 Recursively find the address range of a resource, performing
429 address translation for resources that are located behind
435 Resource previously added to this memory map or any windows.
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.
447 Raises :exn:`KeyError` if the resource is not found.
449 if resource
in self
._resources
:
450 resource_range
= self
._resources
[resource
]
451 return resource_range
.start
, resource_range
.stop
, self
.data_width
453 for window
, window_range
in self
._windows
.items():
455 return self
._translate
(*window
.find_resource(resource
),
461 raise KeyError(resource
)
463 def decode_address(self
, address
):
464 """Decode an address to a resource.
473 A resource mapped to the provided address, or ``None`` if there
476 assignment
= self
._ranges
.get(address
)
477 if assignment
is None:
480 if assignment
in self
._resources
:
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
)
487 assert False # :nocov: