c7214e0e4eed34a00f5ec56beda101c2d4e38eee
4 __all__
= ["MemoryMap"]
10 A range map is a mapping from non-overlapping ranges to arbitrary values.
18 def insert(self
, key
, value
):
19 assert isinstance(key
, range)
20 assert not self
.overlaps(key
)
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
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
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
]
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
]]
44 for key
in self
._keys
:
45 yield key
, self
._values
[key
]
51 A memory map is a hierarchical description of an address space, describing the structure of
52 address decoders of peripherals as well as bus bridges. It is built by adding resources
53 (range allocations for registers, memory, etc) and windows (range allocations for bus bridges),
54 and can be queried later to determine the address of any given resource from a specific
55 vantage point in the design.
60 To simplify address assignment, each memory map has an implicit next address, starting at 0.
61 If a resource or a window is added without specifying an address explicitly, the implicit next
62 address is used. In any case, the implicit next address is set to the address immediately
63 following the newly added resource or window.
72 Range alignment. Each added resource and window will be placed at an address that is
73 a multiple of ``2 ** alignment``, and its size will be rounded up to be a multiple of
76 def __init__(self
, *, addr_width
, data_width
, alignment
=0):
77 if not isinstance(addr_width
, int) or addr_width
<= 0:
78 raise ValueError("Address width must be a positive integer, not {!r}"
80 if not isinstance(data_width
, int) or data_width
<= 0:
81 raise ValueError("Data width must be a positive integer, not {!r}"
83 if not isinstance(alignment
, int) or alignment
< 0:
84 raise ValueError("Alignment must be a non-negative integer, not {!r}"
87 self
.addr_width
= addr_width
88 self
.data_width
= data_width
89 self
.alignment
= alignment
91 self
._ranges
= _RangeMap()
92 self
._resources
= dict()
93 self
._windows
= dict()
98 def _align_up(value
, alignment
):
99 if value
% (1 << alignment
) != 0:
100 value
+= (1 << alignment
) - (value
% (1 << alignment
))
103 def align_to(self
, alignment
):
104 """Align the implicit next address.
109 Address alignment. The start of the implicit next address will be a multiple of
110 ``2 ** max(alignment, self.alignment)``.
114 Implicit next address.
116 if not isinstance(alignment
, int) or alignment
< 0:
117 raise ValueError("Alignment must be a non-negative integer, not {!r}"
119 self
._next
_addr
= self
._align
_up
(self
._next
_addr
, max(alignment
, self
.alignment
))
120 return self
._next
_addr
122 def _compute_addr_range(self
, addr
, size
, step
=1, *, alignment
):
124 if not isinstance(addr
, int) or addr
< 0:
125 raise ValueError("Address must be a non-negative integer, not {!r}"
127 if addr
% (1 << self
.alignment
) != 0:
128 raise ValueError("Explicitly specified address {:#x} must be a multiple of "
130 .format(addr
, 1 << alignment
))
132 addr
= self
._align
_up
(self
._next
_addr
, alignment
)
134 if not isinstance(size
, int) or size
< 0:
135 raise ValueError("Size must be a non-negative integer, not {!r}"
137 size
= self
._align
_up
(size
, alignment
)
139 if addr
> (1 << self
.addr_width
) or addr
+ size
> (1 << self
.addr_width
):
140 raise ValueError("Address range {:#x}..{:#x} out of bounds for memory map spanning "
141 "range {:#x}..{:#x} ({} address bits)"
142 .format(addr
, addr
+ size
, 0, 1 << self
.addr_width
, self
.addr_width
))
144 addr_range
= range(addr
, addr
+ size
, step
)
145 overlaps
= self
._ranges
.overlaps(addr_range
)
148 for overlap
in overlaps
:
149 if overlap
in self
._resources
:
150 resource_range
= self
._resources
[overlap
]
151 overlap_descrs
.append("resource {!r} at {:#x}..{:#x}"
152 .format(overlap
, resource_range
.start
, resource_range
.stop
))
153 if overlap
in self
._windows
:
154 window_range
= self
._windows
[overlap
]
155 overlap_descrs
.append("window {!r} at {:#x}..{:#x}"
156 .format(overlap
, window_range
.start
, window_range
.stop
))
157 raise ValueError("Address range {:#x}..{:#x} overlaps with {}"
158 .format(addr
, addr
+ size
, ", ".join(overlap_descrs
)))
162 def add_resource(self
, resource
, *, size
, addr
=None, alignment
=None):
165 A resource is any device on the bus that is a destination for bus transactions, e.g.
166 a register or a memory block.
171 Arbitrary object representing a resource.
173 Address of the resource. If ``None``, the implicit next address will be used.
174 Otherwise, the exact specified address (which must be a multiple of
175 ``2 ** max(alignment, self.alignment)``) will be used.
177 Size of the resource, in minimal addressable units. Rounded up to a multiple of
178 ``2 ** max(alignment, self.alignment)``.
179 alignment : int or None
180 Alignment of the resource. If not specified, the memory map alignment is used.
184 A tuple ``(start, end)`` describing the address range assigned to the resource.
188 Raises :exn:`ValueError` if the requested address and size, after alignment, would overlap
189 with any resources or windows that have already been added, or would be out of bounds.
191 if resource
in self
._resources
:
192 addr_range
= self
._resources
[resource
]
193 raise ValueError("Resource {!r} is already added at address range {:#x}..{:#x}"
194 .format(resource
, addr_range
.start
, addr_range
.stop
))
196 if alignment
is not None:
197 if not isinstance(alignment
, int) or alignment
< 0:
198 raise ValueError("Alignment must be a non-negative integer, not {!r}"
200 alignment
= max(alignment
, self
.alignment
)
202 alignment
= self
.alignment
204 addr_range
= self
._compute
_addr
_range
(addr
, size
, alignment
=alignment
)
205 self
._ranges
.insert(addr_range
, resource
)
206 self
._resources
[resource
] = addr_range
207 self
._next
_addr
= addr_range
.stop
208 return addr_range
.start
, addr_range
.stop
211 """Iterate local resources and their address ranges.
213 Non-recursively iterate resources in ascending order of their address.
217 A tuple ``resource, (start, end)`` describing the address range assigned to the resource.
219 for resource
, resource_range
in self
._resources
.items():
220 yield resource
, (resource_range
.start
, resource_range
.stop
)
222 def add_window(self
, window
, *, addr
=None, sparse
=None):
225 A window is a device on a bus that provides access to a different bus, i.e. a bus bridge.
226 It performs address translation, such that the devices on a subordinate bus have different
227 addresses; the memory map reflects this address translation when resources are looked up
233 If a narrow bus is bridged to a wide bus, the bridge can perform *sparse* or *dense*
234 address translation. In the sparse case, each transaction on the wide bus results in
235 one transaction on the narrow bus; high data bits on the wide bus are ignored, and any
236 contiguous resource on the narrow bus becomes discontiguous on the wide bus. In the dense
237 case, each transaction on the wide bus results in several transactions on the narrow bus,
238 and any contiguous resource on the narrow bus stays contiguous on the wide bus.
242 window : :class:`MemoryMap`
243 A memory map describing the layout of the window.
245 Address of the window. If ``None``, the implicit next address will be used after
246 aligning it to ``2 ** window.addr_width``. Otherwise, the exact specified address
247 (which must be a multiple of ``2 ** window.addr_width``) will be used.
248 sparse : bool or None
249 Address translation type. Ignored if the datapath widths of both memory maps are
250 equal; must be specified otherwise.
254 A tuple ``(start, end, ratio)`` describing the address range assigned to the window.
255 When bridging buses of unequal data width, ``ratio`` is the amount of contiguous addresses
256 on the narrower bus that are accessed for each transaction on the wider bus. Otherwise,
261 Raises :exn:`ValueError` if the requested address and size, after alignment, would overlap
262 with any resources or windows that have already been added, or would be out of bounds;
263 if the added memory map has wider datapath than this memory map; if dense address
264 translation is used and the datapath width of this memory map is not an integer multiple
265 of the datapath width of the added memory map.
267 if not isinstance(window
, MemoryMap
):
268 raise TypeError("Window must be a MemoryMap, not {!r}"
270 if window
in self
._windows
:
271 addr_range
= self
._windows
[window
]
272 raise ValueError("Window {!r} is already added at address range {:#x}..{:#x}"
273 .format(window
, addr_range
.start
, addr_range
.stop
))
275 if window
.data_width
> self
.data_width
:
276 raise ValueError("Window has data width {}, and cannot be added to a memory map "
278 .format(window
.data_width
, self
.data_width
))
279 if window
.data_width
!= self
.data_width
:
281 raise ValueError("Address translation mode must be explicitly specified "
282 "when adding a window with data width {} to a memory map "
284 .format(window
.data_width
, self
.data_width
))
285 if not sparse
and self
.data_width
% window
.data_width
!= 0:
286 raise ValueError("Dense addressing cannot be used because the memory map "
287 "data width {} is not an integer multiple of window "
289 .format(self
.data_width
, window
.data_width
))
292 ratio
= self
.data_width
// window
.data_width
295 size
= (1 << window
.addr_width
) // ratio
296 # For resources, the alignment argument of add_resource() affects both address and size
297 # of the resource; aligning only the address should be done using align_to(). For windows,
298 # changing the size (beyond the edge case of the window size being smaller than alignment
299 # of the bus) is unlikely to be useful, so there is no alignment argument. The address of
300 # a window can still be aligned using align_to().
301 alignment
= max(self
.alignment
, window
.addr_width
// ratio
)
303 addr_range
= self
._compute
_addr
_range
(addr
, size
, ratio
, alignment
=alignment
)
304 self
._ranges
.insert(addr_range
, window
)
305 self
._windows
[window
] = addr_range
306 self
._next
_addr
= addr_range
.stop
307 return addr_range
.start
, addr_range
.stop
, addr_range
.step
310 """Iterate local windows and their address ranges.
312 Non-recursively iterate windows in ascending order of their address.
316 A tuple ``window, (start, end, ratio)`` describing the address range assigned to
317 the window. When bridging buses of unequal data width, ``ratio`` is the amount of
318 contiguous addresses on the narrower bus that are accessed for each transaction on
319 the wider bus. Otherwise, it is always 1.
321 for window
, window_range
in self
._windows
.items():
322 yield window
, (window_range
.start
, window_range
.stop
, window_range
.step
)
325 def _translate(start
, end
, width
, window
, window_range
):
326 assert (end
- start
) % window_range
.step
== 0
327 # Accessing a resource through a dense and then a sparse window results in very strange
328 # layouts that cannot be easily represented, so reject those.
329 assert window_range
.step
== 1 or width
== window
.data_width
330 size
= (end
- start
) // window_range
.step
331 start
+= window_range
.start
332 width
*= window_range
.step
333 return start
, start
+ size
, width
335 def all_resources(self
):
336 """Iterate all resources and their address ranges.
338 Recursively iterate all resources in ascending order of their address, performing address
339 translation for resources that are located behind a window.
343 A tuple ``resource, (start, end, width)`` describing the address range assigned to
344 the resource. ``width`` is the amount of data bits accessed at each address, which may be
345 equal to ``self.data_width``, or less if the resource is located behind a window that
346 uses sparse addressing.
348 for addr_range
, assignment
in self
._ranges
.items():
349 if assignment
in self
._resources
:
350 yield assignment
, (addr_range
.start
, addr_range
.stop
, self
.data_width
)
351 elif assignment
in self
._windows
:
352 for sub_resource
, sub_descr
in assignment
.all_resources():
353 yield sub_resource
, self
._translate
(*sub_descr
, assignment
, addr_range
)
355 assert False # :nocov:
357 def find_resource(self
, resource
):
358 """Find address range corresponding to a resource.
360 Recursively find the address range of a resource, performing address translation for
361 resources that are located behind a window.
366 Resource previously added to this memory map or any windows.
370 A tuple ``(start, end, width)`` describing the address range assigned to the resource.
371 ``width`` is the amount of data bits accessed at each address, which may be equal to
372 ``self.data_width``, or less if the resource is located behind a window that uses sparse
377 Raises :exn:`KeyError` if the resource is not found.
379 if resource
in self
._resources
:
380 resource_range
= self
._resources
[resource
]
381 return resource_range
.start
, resource_range
.stop
, self
.data_width
383 for window
, window_range
in self
._windows
.items():
385 return self
._translate
(*window
.find_resource(resource
), window
, window_range
)
389 raise KeyError(resource
)
391 def decode_address(self
, address
):
392 """Decode an address to a resource.
401 A resource mapped to the provided address, or ``None`` if there is no such resource.
403 assignment
= self
._ranges
.get(address
)
404 if assignment
is None:
407 if assignment
in self
._resources
:
409 elif assignment
in self
._windows
:
410 addr_range
= self
._windows
[assignment
]
411 return assignment
.decode_address((address
- addr_range
.start
) // addr_range
.step
)
413 assert False # :nocov: