1 /*
2 * Copyright 2008, Salvatore Benedetto, salvatore.benedetto@gmail.com
3 * Copyright 2003, Tyler Dauwalder, tyler@dauwalder.net.
4 * Distributed under the terms of the MIT License.
5 */
6
7 #ifndef _UDF_ALLOCATION_DESCRIPTOR_LIST_H
8 #define _UDF_ALLOCATION_DESCRIPTOR_LIST_H
9
10 /*! \file AllocationDescriptorList.h */
11
12 #include "UdfDebug.h"
13
14 #include "Icb.h"
15 #include "UdfStructures.h"
16 #include "Volume.h"
17
18 #include <util/kernel_cpp.h>
19
20 /*! \brief Common interface for dealing with the three standard
21 forms of allocation descriptors used in UDF icbs.
22
23 The \c Accessor class is an allocation descriptor accessor class
24 for the allocation scheme of interest. Instances of it should be
25 passable by value, and should define the following public members:
26 - typedef DescriptorType;
27 - inline uint8 GetType(DescriptorType &descriptor);
28 - inline uint32 GetBlock(DescriptorType &descriptor);
29 - inline uint16 GetPartition(DescriptorType &descriptor);
30 - inline uint32 GetLength(DescriptorType &descriptor);
31 */
32 template <class Accessor>
33 class AllocationDescriptorList {
34 private:
35 typedef typename Accessor::DescriptorType Descriptor;
36
37 public:
38 AllocationDescriptorList(Icb *icb,
39 Accessor accessor = Accessor());
40
41 status_t FindExtent(off_t start, long_address *extent,
42 bool *isEmpty);
43
44 private:
45
_BlockIndex()46 off_t _BlockIndex() const { return fBlockIndex; }
47 Descriptor *_CurrentDescriptor() const;
48 Descriptor *_DescriptorArray() const;
49 size_t _DescriptorArraySize() const;
_DescriptorIndex()50 int32 _DescriptorIndex() const { return fDescriptorIndex; }
_DescriptorNumber()51 int32 _DescriptorNumber() const { return fDescriptorNumber; }
52 status_t _MoveToNextDescriptor();
53 void _Rewind();
54 void _WalkContinuationChain(Descriptor *descriptor);
55
56 Accessor fAccessor;
57 CachedBlock fAdditionalDescriptors;
58 off_t fBlockIndex;
59 int32 fDescriptorIndex;
60 int32 fDescriptorNumber;
61 Icb *fIcb;
62 Descriptor *fIcbDescriptors;
63 int32 fIcbDescriptorsSize;
64 bool fReadFromIcb;
65 Volume *fVolume;
66 };
67
68
69 template<class Accessor>
AllocationDescriptorList(Icb * icb,Accessor accessor)70 AllocationDescriptorList<Accessor>::AllocationDescriptorList(Icb *icb,
71 Accessor accessor)
72 :
73 fAccessor(accessor),
74 fAdditionalDescriptors(icb->GetVolume()),
75 fBlockIndex(0),
76 fDescriptorIndex(0),
77 fDescriptorNumber(0),
78 fIcb(icb),
79 fIcbDescriptors((Descriptor *)icb->AllocationDescriptors()),
80 fIcbDescriptorsSize(icb->AllocationDescriptorsSize()),
81 fReadFromIcb(true),
82 fVolume(icb->GetVolume())
83 {
84 TRACE(("AllocationDescriptorList<>::AllocationDescriptorList\n"));
85 _WalkContinuationChain(_CurrentDescriptor());
86 }
87
88
89 /*! \brief Finds the extent for the given address in the stream,
90 returning it in the address pointed to by \a blockRun.
91
92 \param start The byte address of interest
93 \param extent The extent containing the stream address given
94 by \c start.
95 \param isEmpty If set to true, indicates that the given extent is
96 unrecorded and thus its contents should be interpreted
97 as all zeros.
98 */
99 template<class Accessor>
100 status_t
FindExtent(off_t start,long_address * extent,bool * isEmpty)101 AllocationDescriptorList<Accessor>::FindExtent(off_t start,
102 long_address *extent, bool *isEmpty)
103 {
104 TRACE(("AllocationDescriptorList<>::FindExtent: start: %" B_PRIdOFF ", "
105 "extent: %p, isEmpty: %p\n", start, extent, isEmpty));
106
107 off_t startBlock = start >> fVolume->BlockShift();
108
109 // This should never have to happen, as FindExtent is only called by
110 // Icb::_Read() sequentially, as a file read is performed, but you
111 // never know. :-)
112 if (startBlock < _BlockIndex())
113 _Rewind();
114
115 status_t status = B_OK;
116 while (true) {
117 Descriptor *descriptor = _CurrentDescriptor();
118 if (descriptor) {
119 if (_BlockIndex() <= startBlock && startBlock
120 < _BlockIndex() + fAccessor.GetLength(*descriptor)) {
121 // The start block is somewhere in this extent, so return
122 // the applicable tail end portion.
123 off_t offset = startBlock - _BlockIndex();
124 extent->set_block(fAccessor.GetBlock(*descriptor) + offset);
125 extent->set_partition(fAccessor.GetPartition(*descriptor));
126 extent->set_length(fAccessor.GetLength(*descriptor)
127 - (offset*fVolume->BlockSize()));
128 extent->set_type(fAccessor.GetType(*descriptor));
129 break;
130 } else {
131 _MoveToNextDescriptor();
132 }
133 } else {
134 TRACE_ERROR(("AllocationDescriptorList<>::FindExtent: "
135 "Descriptor #%" B_PRId32 " found NULL\n",
136 _DescriptorNumber()));
137 status = B_ERROR;
138 break;
139 }
140 }
141
142 return status;
143 }
144
145
146 // #pragma - Private methods
147
148
149 template<class Accessor>
150 typename AllocationDescriptorList<Accessor>::Descriptor*
_CurrentDescriptor()151 AllocationDescriptorList<Accessor>::_CurrentDescriptor() const
152 {
153 TRACE(("AllocationDescriptorList<>::_CurrentDescriptor:\n"
154 "\t_DescriptorIndex() + 1 * sizeof(Descriptor) = %ld\n"
155 "\t_DescriptorArraySize() = %ld\n"
156 "\t_DescriptorArray() = %p\n",
157 (_DescriptorIndex() + 1) * sizeof(Descriptor),
158 _DescriptorArraySize(), _DescriptorArray()));
159
160 return ((_DescriptorIndex() + 1) * sizeof(Descriptor)
161 <= _DescriptorArraySize())
162 ? &(_DescriptorArray()[_DescriptorIndex()])
163 : NULL;
164 }
165
166
167 template<class Accessor>
168 status_t
_MoveToNextDescriptor()169 AllocationDescriptorList<Accessor>::_MoveToNextDescriptor()
170 {
171 Descriptor* descriptor = _CurrentDescriptor();
172 if (!descriptor)
173 return B_ENTRY_NOT_FOUND;
174
175 // Increment our indices and get the next descriptor
176 // from this extent.
177 fBlockIndex += fAccessor.GetLength(*descriptor);
178 fDescriptorIndex++;
179 fDescriptorNumber++;
180 descriptor = _CurrentDescriptor();
181
182 // If no such descriptor exists, we've run out of
183 // descriptors in this extent, and we're done. The
184 // next time _CurrentDescriptor() is called, it will
185 // return NULL, signifying this. Otherwise, we have to
186 // see if the new descriptor identifies the next extent
187 // of allocation descriptors, in which case we have to
188 // load up the appropriate extent (guaranteed to be at
189 // most one block in length by UDF-2.01 5.1 and UDF-2.01
190 // 2.3.11).
191 _WalkContinuationChain(descriptor);
192
193 return B_ERROR;
194 }
195
196
197 template<class Accessor>
198 void
_WalkContinuationChain(Descriptor * descriptor)199 AllocationDescriptorList<Accessor>::_WalkContinuationChain(Descriptor *descriptor)
200 {
201 TRACE(("AllocationDescriptorList<>::_WalkContinuationChain: descriptor = %p\n",
202 descriptor));
203 if (descriptor
204 && fAccessor.GetType(*descriptor) == EXTENT_TYPE_CONTINUATION) {
205 // Load the new block, make sure we're not trying
206 // to read from the icb descriptors anymore, and
207 // reset the descriptor index.
208 fAdditionalDescriptors.SetTo(fAccessor, *descriptor);
209 fReadFromIcb = false;
210 fDescriptorIndex = 0;
211
212 // Make sure that the first descriptor in this extent isn't
213 // another continuation. That would be stupid, but not
214 // technically illegal.
215 _WalkContinuationChain(_CurrentDescriptor());
216 }
217 }
218
219
220 template<class Accessor>
221 void
_Rewind()222 AllocationDescriptorList<Accessor>::_Rewind()
223 {
224 fDescriptorIndex = 0;
225 fDescriptorNumber = 0;
226 fReadFromIcb = true;
227 }
228
229
230 template<class Accessor>
231 typename AllocationDescriptorList<Accessor>::Descriptor*
_DescriptorArray()232 AllocationDescriptorList<Accessor>::_DescriptorArray() const
233 {
234 return fReadFromIcb ? fIcbDescriptors
235 : (typename AllocationDescriptorList<Accessor>::Descriptor *)
236 fAdditionalDescriptors.Block();
237 }
238
239
240 template<class Accessor>
241 size_t
_DescriptorArraySize()242 AllocationDescriptorList<Accessor>::_DescriptorArraySize() const
243 {
244 return fReadFromIcb ? fIcbDescriptorsSize
245 : fAdditionalDescriptors.BlockSize();
246 }
247
248
249 // pragma - Accessors
250
251
252 class ShortDescriptorAccessor {
253 public:
ShortDescriptorAccessor(uint16 partition)254 ShortDescriptorAccessor(uint16 partition)
255 :
256 fPartition(partition)
257 {
258 }
259
260 typedef short_address DescriptorType;
261
GetBlock(DescriptorType & descriptor)262 inline uint32 GetBlock(DescriptorType &descriptor) const
263 {
264 return descriptor.block();
265 }
266
GetLength(DescriptorType & descriptor)267 inline uint32 GetLength(DescriptorType &descriptor) const
268 {
269 return descriptor.length();
270 }
271
GetPartition(DescriptorType & descriptor)272 inline uint16 GetPartition(DescriptorType &descriptor) const
273 {
274 return fPartition;
275 }
276
GetType(DescriptorType & descriptor)277 inline uint8 GetType(DescriptorType &descriptor) const
278 {
279 return descriptor.type();
280 }
281
282 private:
283 uint16 fPartition;
284 };
285
286
287 class LongDescriptorAccessor {
288 public:
289 typedef long_address DescriptorType;
290
GetBlock(DescriptorType & descriptor)291 inline uint32 GetBlock(DescriptorType &descriptor) const
292 {
293 return descriptor.block();
294 }
295
GetLength(DescriptorType & descriptor)296 inline uint32 GetLength(DescriptorType &descriptor) const
297 {
298 return descriptor.length();
299 }
300
GetPartition(DescriptorType & descriptor)301 inline uint16 GetPartition(DescriptorType &descriptor) const
302 {
303 return descriptor.partition();
304 }
305
GetType(DescriptorType & descriptor)306 inline uint8 GetType(DescriptorType &descriptor) const
307 {
308 return descriptor.type();
309 }
310 };
311
312 #endif // _UDF_ALLOCATION_DESCRIPTOR_LIST_H
313