1#include "Recognition.h"
2
3#include "UdfString.h"
4#include "MemoryChunk.h"
5#include "Utils.h"
6
7using namespace Udf;
8
9//------------------------------------------------------------------------------
10// forward declarations
11//------------------------------------------------------------------------------
12
13static status_t
14walk_volume_recognition_sequence(int device, off_t offset,
15                                 uint32 blockSize,
16                                 uint32 blockShift);
17static status_t
18walk_anchor_volume_descriptor_sequences(int device, off_t offset, off_t length,
19                                        uint32 blockSize, uint32 blockShift,
20                                        logical_volume_descriptor &logicalVolumeDescriptor,
21							            partition_descriptor partitionDescriptors[],
22							            uint8 &partitionDescriptorCount);
23static status_t
24walk_volume_descriptor_sequence(extent_address descriptorSequence,
25								int device, uint32 blockSize, uint32 blockShift,
26							    logical_volume_descriptor &logicalVolumeDescriptor,
27							    partition_descriptor partitionDescriptors[],
28							    uint8 &partitionDescriptorCount);
29
30static status_t
31walk_integrity_sequence(int device, uint32 blockSize, uint32 blockShift,
32                        extent_address descriptorSequence, uint32 sequenceNumber = 0);
33
34//------------------------------------------------------------------------------
35// externally visible functions
36//------------------------------------------------------------------------------
37
38status_t
39Udf::udf_recognize(int device, off_t offset, off_t length, uint32 blockSize,
40                   uint32 &blockShift, logical_volume_descriptor &logicalVolumeDescriptor,
41				   partition_descriptor partitionDescriptors[],
42				   uint8 &partitionDescriptorCount)
43{
44	DEBUG_INIT_ETC(NULL, ("device: %d, offset: %Ld, length: %Ld, "
45	               "blockSize: %ld, [...descriptors, etc...]", device, offset,
46	               length, blockSize));
47
48	// Check the block size
49	status_t error = get_block_shift(blockSize, blockShift);
50	if (!error) {
51		PRINT(("blockShift: %ld\n", blockShift));
52
53		// Check for a valid volume recognition sequence
54		error = walk_volume_recognition_sequence(device, offset, blockSize, blockShift);
55
56		// Now hunt down a volume descriptor sequence from one of
57		// the anchor volume pointers (if there are any).
58		if (!error) {
59			error = walk_anchor_volume_descriptor_sequences(device, offset, length,
60			                                                blockSize, blockShift,
61			                                                logicalVolumeDescriptor,
62			                                                partitionDescriptors,
63			                                                partitionDescriptorCount);
64		}
65
66		// Now walk the integrity sequence and make sure the last integrity
67		// descriptor is a closed descriptor
68		if (!error) {
69			error = walk_integrity_sequence(device, blockSize, blockShift,
70			                                logicalVolumeDescriptor.integrity_sequence_extent());
71		}
72	} else {
73		PRINT(("Block size must be a positive power of two! (blockSize = %ld)\n", blockSize));
74	}
75
76	RETURN(error);
77}
78
79status_t
80Udf::udf_recognize(int device, off_t offset, off_t length, uint32 blockSize,
81                   char *volumeName)
82{
83	DEBUG_INIT_ETC(NULL, ("device: %d, offset: %Ld, length: %Ld, "
84	               "blockSize: %ld, volumeName: %p", device, offset, length,
85	               blockSize, volumeName));
86	logical_volume_descriptor logicalVolumeDescriptor;
87	partition_descriptor partitionDescriptors[Udf::kMaxPartitionDescriptors];
88	uint8 partitionDescriptorCount;
89	uint32 blockShift;
90	status_t error = udf_recognize(device, offset, length, blockSize, blockShift,
91	                               logicalVolumeDescriptor, partitionDescriptors,
92	                               partitionDescriptorCount);
93	if (!error && volumeName) {
94		String name(logicalVolumeDescriptor.logical_volume_identifier());
95		strcpy(volumeName, name.Utf8());
96	}
97	RETURN(error);
98}
99
100//------------------------------------------------------------------------------
101// local functions
102//------------------------------------------------------------------------------
103
104static
105status_t
106walk_volume_recognition_sequence(int device, off_t offset, uint32 blockSize, uint32 blockShift)
107{
108	DEBUG_INIT(NULL);
109	// vrs starts at block 16. Each volume structure descriptor (vsd)
110	// should be one block long. We're expecting to find 0 or more iso9660
111	// vsd's followed by some ECMA-167 vsd's.
112	MemoryChunk chunk(blockSize);
113	status_t error = chunk.InitCheck();
114	if (!error) {
115		bool foundISO = false;
116		bool foundExtended = false;
117		bool foundECMA167 = false;
118		bool foundECMA168 = false;
119		bool foundBoot = false;
120		for (uint32 block = 16; true; block++) {
121	    	PRINT(("block %ld: ", block))
122			off_t address = (offset + block) << blockShift;
123			ssize_t bytesRead = read_pos(device, address, chunk.Data(), blockSize);
124			if (bytesRead == (ssize_t)blockSize)
125		    {
126		    	volume_structure_descriptor_header* descriptor =
127		    	  reinterpret_cast<volume_structure_descriptor_header*>(chunk.Data());
128				if (descriptor->id_matches(kVSDID_ISO)) {
129					SIMPLE_PRINT(("found ISO9660 descriptor\n"));
130					foundISO = true;
131				} else if (descriptor->id_matches(kVSDID_BEA)) {
132					SIMPLE_PRINT(("found BEA descriptor\n"));
133					foundExtended = true;
134				} else if (descriptor->id_matches(kVSDID_TEA)) {
135					SIMPLE_PRINT(("found TEA descriptor\n"));
136					foundExtended = true;
137				} else if (descriptor->id_matches(kVSDID_ECMA167_2)) {
138					SIMPLE_PRINT(("found ECMA-167 rev 2 descriptor\n"));
139					foundECMA167 = true;
140				} else if (descriptor->id_matches(kVSDID_ECMA167_3)) {
141					SIMPLE_PRINT(("found ECMA-167 rev 3 descriptor\n"));
142					foundECMA167 = true;
143				} else if (descriptor->id_matches(kVSDID_BOOT)) {
144					SIMPLE_PRINT(("found boot descriptor\n"));
145					foundBoot = true;
146				} else if (descriptor->id_matches(kVSDID_ECMA168)) {
147					SIMPLE_PRINT(("found ECMA-168 descriptor\n"));
148					foundECMA168 = true;
149				} else {
150					SIMPLE_PRINT(("found invalid descriptor, id = `%.5s'\n", descriptor->id));
151					break;
152				}
153			} else {
154				SIMPLE_PRINT(("read_pos(pos:%Ld, len:%ld) failed with: 0x%lx\n", address,
155				        blockSize, bytesRead));
156				break;
157			}
158		}
159
160		// If we find an ECMA-167 descriptor, OR if we find a beginning
161		// or terminating extended area descriptor with NO ECMA-168
162		// descriptors, we return B_OK to signal that we should go
163		// looking for valid anchors.
164		error = foundECMA167 || (foundExtended && !foundECMA168) ? B_OK : B_ERROR;
165	}
166
167	RETURN(error);
168}
169
170static
171status_t
172walk_anchor_volume_descriptor_sequences(int device, off_t offset, off_t length,
173                                        uint32 blockSize, uint32 blockShift,
174                                        logical_volume_descriptor &logicalVolumeDescriptor,
175							            partition_descriptor partitionDescriptors[],
176							            uint8 &partitionDescriptorCount)
177{
178	DEBUG_INIT(NULL);
179	const uint8 avds_location_count = 4;
180	const off_t avds_locations[avds_location_count] = {
181														256,
182	                                                    length-1-256,
183	                                                    length-1,
184	                                                    512,
185	                                                  };
186	bool found_vds = false;
187	for (int32 i = 0; i < avds_location_count; i++) {
188		off_t block = avds_locations[i];
189		off_t address = (offset + block) << blockShift;
190		MemoryChunk chunk(blockSize);
191		anchor_volume_descriptor *anchor = NULL;
192
193		status_t anchorErr = chunk.InitCheck();
194		if (!anchorErr) {
195			ssize_t bytesRead = read_pos(device, address, chunk.Data(), blockSize);
196			anchorErr = bytesRead == (ssize_t)blockSize ? B_OK : B_IO_ERROR;
197			if (anchorErr) {
198				PRINT(("block %Ld: read_pos(pos:%Ld, len:%ld) failed with error 0x%lx\n",
199				       block, address, blockSize, bytesRead));
200			}
201		}
202		if (!anchorErr) {
203			anchor = reinterpret_cast<anchor_volume_descriptor*>(chunk.Data());
204			anchorErr = anchor->tag().init_check(block+offset);
205			if (anchorErr) {
206				PRINT(("block %Ld: invalid anchor\n", block));
207			} else {
208				PRINT(("block %Ld: valid anchor\n", block));
209			}
210		}
211		if (!anchorErr) {
212			PRINT(("block %Ld: anchor:\n", block));
213			PDUMP(anchor);
214			// Found an avds, so try the main sequence first, then
215			// the reserve sequence if the main one fails.
216			anchorErr = walk_volume_descriptor_sequence(anchor->main_vds(), device,
217														blockSize, blockShift,
218			                                            logicalVolumeDescriptor,
219			                                            partitionDescriptors,
220			                                            partitionDescriptorCount);
221			if (anchorErr)
222				anchorErr = walk_volume_descriptor_sequence(anchor->reserve_vds(), device,
223															blockSize, blockShift,
224			                                            	logicalVolumeDescriptor,
225			                                            	partitionDescriptors,
226			                                            	partitionDescriptorCount);
227		}
228		if (!anchorErr) {
229			PRINT(("block %Ld: found valid vds\n", avds_locations[i]));
230			found_vds = true;
231			break;
232		} else {
233			// Both failed, so loop around and try another avds
234			PRINT(("block %Ld: vds search failed\n", avds_locations[i]));
235		}
236	}
237	status_t error = found_vds ? B_OK : B_ERROR;
238	RETURN(error);
239}
240
241static
242status_t
243walk_volume_descriptor_sequence(extent_address descriptorSequence,
244								int device, uint32 blockSize, uint32 blockShift,
245							    logical_volume_descriptor &logicalVolumeDescriptor,
246							    partition_descriptor partitionDescriptors[],
247							    uint8 &partitionDescriptorCount)
248{
249	DEBUG_INIT_ETC(NULL, ("descriptorSequence.loc:%ld, descriptorSequence.len:%ld",
250	           descriptorSequence.location(), descriptorSequence.length()));
251	uint32 count = descriptorSequence.length() >> blockShift;
252
253	bool foundLogicalVolumeDescriptor = false;
254	bool foundUnallocatedSpaceDescriptor = false;
255	bool foundUdfImplementationUseDescriptor = false;
256	uint8 uniquePartitions = 0;
257	status_t error = B_OK;
258
259	for (uint32 i = 0; i < count; i++)
260	{
261		off_t block = descriptorSequence.location()+i;
262		off_t address = block << blockShift;
263		MemoryChunk chunk(blockSize);
264		descriptor_tag  *tag = NULL;
265
266		PRINT(("descriptor #%ld (block %Ld):\n", i, block));
267
268		status_t loopError = chunk.InitCheck();
269		if (!loopError) {
270			ssize_t bytesRead = read_pos(device, address, chunk.Data(), blockSize);
271			loopError = bytesRead == (ssize_t)blockSize ? B_OK : B_IO_ERROR;
272			if (loopError) {
273				PRINT(("block %Ld: read_pos(pos:%Ld, len:%ld) failed with error 0x%lx\n",
274				       block, address, blockSize, bytesRead));
275			}
276		}
277		if (!loopError) {
278			tag = reinterpret_cast<descriptor_tag *>(chunk.Data());
279			loopError = tag->init_check(block);
280		}
281		if (!loopError) {
282			// Now decide what type of descriptor we have
283			switch (tag->id()) {
284				case TAGID_UNDEFINED:
285					break;
286
287				case TAGID_PRIMARY_VOLUME_DESCRIPTOR:
288				{
289					primary_volume_descriptor *primary = reinterpret_cast<primary_volume_descriptor*>(tag);
290					PDUMP(primary);
291					(void)primary;	// kill the warning
292					break;
293				}
294
295				case TAGID_ANCHOR_VOLUME_DESCRIPTOR_POINTER:
296					break;
297
298				case TAGID_VOLUME_DESCRIPTOR_POINTER:
299					break;
300
301				case TAGID_IMPLEMENTATION_USE_VOLUME_DESCRIPTOR:
302				{
303					implementation_use_descriptor *impUse = reinterpret_cast<implementation_use_descriptor*>(tag);
304					PDUMP(impUse);
305					// Check for a matching implementation id string (note that the
306					// revision version is not checked)
307					if (impUse->tag().init_check(block) == B_OK
308					    && impUse->implementation_id().matches(kLogicalVolumeInfoId201))
309					{
310							foundUdfImplementationUseDescriptor = true;
311					}
312					break;
313				}
314
315				case TAGID_PARTITION_DESCRIPTOR:
316				{
317					partition_descriptor *partition = reinterpret_cast<partition_descriptor*>(tag);
318					PDUMP(partition);
319					if (partition->tag().init_check(block) == B_OK) {
320						// Check for a previously discovered partition descriptor with
321						// the same number as this partition. If found, keep the one with
322						// the higher vds number.
323						bool foundDuplicate = false;
324						int num;
325						for (num = 0; num < uniquePartitions; num++) {
326							if (partitionDescriptors[num].partition_number()
327							    == partition->partition_number())
328							{
329								foundDuplicate = true;
330								if (partitionDescriptors[num].vds_number()
331								    < partition->vds_number())
332								{
333									partitionDescriptors[num] = *partition;
334									PRINT(("Replacing previous partition #%d (vds_number: %ld) with "
335									       "new partition #%d (vds_number: %ld)\n",
336									       partitionDescriptors[num].partition_number(),
337									       partitionDescriptors[num].vds_number(),
338									       partition->partition_number(),
339									       partition->vds_number()));
340								}
341								break;
342							}
343						}
344						// If we didn't find a duplicate, see if we have any open descriptor
345						// spaces left.
346						if (!foundDuplicate) {
347							if (num < Udf::kMaxPartitionDescriptors) {
348								// At least one more partition descriptor allowed
349								partitionDescriptors[num] = *partition;
350								uniquePartitions++;
351								PRINT(("Adding partition #%d (vds_number: %ld)\n",
352								       partition->partition_number(),
353								       partition->vds_number()));
354							} else {
355								// We've found more than kMaxPartitionDescriptor uniquely-
356								// numbered partitions. So, search through the partitions
357								// we already have again, this time just looking for a
358								// partition with a lower vds number. If we find one,
359								// replace it with this one. If we don't, scream bloody
360								// murder.
361								bool foundReplacement = false;
362								for (int j = 0; j < uniquePartitions; j++) {
363									if (partitionDescriptors[j].vds_number()
364									    < partition->vds_number())
365									{
366										foundReplacement = true;
367										partitionDescriptors[j] = *partition;
368										PRINT(("Replacing partition #%d (vds_number: %ld) "
369										       "with partition #%d (vds_number: %ld)\n",
370										       partitionDescriptors[j].partition_number(),
371										       partitionDescriptors[j].vds_number(),
372										       partition->partition_number(),
373										       partition->vds_number()));
374										break;
375									}
376								}
377								if (!foundReplacement) {
378									PRINT(("Found more than kMaxPartitionDescriptors == %d "
379									       "unique partition descriptors!\n",
380									       kMaxPartitionDescriptors));
381									error = B_BAD_VALUE;
382									break;
383								}
384							}
385						}
386					}
387					break;
388				}
389
390				case TAGID_LOGICAL_VOLUME_DESCRIPTOR:
391				{
392					logical_volume_descriptor *logical = reinterpret_cast<logical_volume_descriptor*>(tag);
393					PDUMP(logical);
394					if (foundLogicalVolumeDescriptor) {
395						// Keep the vd with the highest vds_number
396						if (logicalVolumeDescriptor.vds_number() < logical->vds_number())
397							logicalVolumeDescriptor = *logical;
398					} else {
399						logicalVolumeDescriptor = *logical;
400						foundLogicalVolumeDescriptor = true;
401					}
402					break;
403				}
404
405				case TAGID_UNALLOCATED_SPACE_DESCRIPTOR:
406				{
407					unallocated_space_descriptor *unallocated = reinterpret_cast<unallocated_space_descriptor*>(tag);
408					PDUMP(unallocated);
409					foundUnallocatedSpaceDescriptor = true;
410					(void)unallocated;	// kill the warning
411					break;
412				}
413
414				case TAGID_TERMINATING_DESCRIPTOR:
415				{
416					terminating_descriptor *terminating = reinterpret_cast<terminating_descriptor*>(tag);
417					PDUMP(terminating);
418					(void)terminating;	// kill the warning
419					break;
420				}
421
422				case TAGID_LOGICAL_VOLUME_INTEGRITY_DESCRIPTOR:
423					// Not found in this descriptor sequence
424					break;
425
426				default:
427					break;
428
429			}
430		}
431	}
432
433	PRINT(("found %d unique partition%s\n", uniquePartitions,
434	       (uniquePartitions == 1 ? "" : "s")));
435
436	if (!error && !foundUdfImplementationUseDescriptor) {
437		INFORM(("WARNING: no valid udf implementation use descriptor found\n"));
438	}
439	if (!error)
440		error = foundLogicalVolumeDescriptor
441		        && foundUnallocatedSpaceDescriptor
442		        ? B_OK : B_ERROR;
443	if (!error)
444		error = uniquePartitions >= 1 ? B_OK : B_ERROR;
445	if (!error)
446		partitionDescriptorCount = uniquePartitions;
447
448	RETURN(error);
449}
450
451/*! \brief Walks the integrity sequence in the extent given by \a descriptorSequence.
452
453	\return
454	- \c B_OK: Success. the sequence was terminated by a valid, closed
455	           integrity descriptor.
456	- \c B_ENTRY_NOT_FOUND: The sequence was empty.
457	- (other error code): The sequence was non-empty and did not end in a valid,
458                          closed integrity descriptor.
459*/
460static status_t
461walk_integrity_sequence(int device, uint32 blockSize, uint32 blockShift,
462                        extent_address descriptorSequence, uint32 sequenceNumber)
463{
464	DEBUG_INIT_ETC(NULL, ("descriptorSequence.loc:%ld, descriptorSequence.len:%ld",
465	           descriptorSequence.location(), descriptorSequence.length()));
466	uint32 count = descriptorSequence.length() >> blockShift;
467
468	bool lastDescriptorWasClosed = false;
469	uint16 highestMinimumUDFReadRevision = 0x0000;
470	status_t error = count > 0 ? B_OK : B_ENTRY_NOT_FOUND;
471	for (uint32 i = 0; error == B_OK && i < count; i++)
472	{
473		off_t block = descriptorSequence.location()+i;
474		off_t address = block << blockShift;
475		MemoryChunk chunk(blockSize);
476		descriptor_tag *tag = NULL;
477
478		PRINT(("integrity descriptor #%ld:%ld (block %Ld):\n", sequenceNumber, i, block));
479
480		status_t loopError = chunk.InitCheck();
481		if (!loopError) {
482			ssize_t bytesRead = read_pos(device, address, chunk.Data(), blockSize);
483			loopError = check_size_error(bytesRead, blockSize);
484			if (loopError) {
485				PRINT(("block %Ld: read_pos(pos:%Ld, len:%ld) failed with error 0x%lx\n",
486				       block, address, blockSize, bytesRead));
487			}
488		}
489		if (!loopError) {
490			tag = reinterpret_cast<descriptor_tag *>(chunk.Data());
491			loopError = tag->init_check(block);
492		}
493		if (!loopError) {
494			// Check the descriptor type and see if it's closed.
495			loopError = tag->id() == TAGID_LOGICAL_VOLUME_INTEGRITY_DESCRIPTOR
496			            ? B_OK : B_BAD_DATA;
497			if (!loopError) {
498				logical_volume_integrity_descriptor *descriptor =
499					reinterpret_cast<logical_volume_integrity_descriptor*>(chunk.Data());
500				PDUMP(descriptor);
501				lastDescriptorWasClosed = descriptor->integrity_type() == INTEGRITY_CLOSED;
502				if (lastDescriptorWasClosed) {
503					uint16 minimumRevision = descriptor->minimum_udf_read_revision();
504					if (minimumRevision > highestMinimumUDFReadRevision) {
505						highestMinimumUDFReadRevision = minimumRevision;
506					} else if (minimumRevision < highestMinimumUDFReadRevision) {
507						INFORM(("WARNING: found decreasing minimum udf read revision in integrity "
508						        "sequence (last highest: 0x%04x, current: 0x%04x); using higher "
509						        "revision.\n", highestMinimumUDFReadRevision, minimumRevision));
510					}
511				}
512
513				// Check a continuation extent if necessary. Note that this effectively
514				// ends our search through this extent
515				extent_address &next = descriptor->next_integrity_extent();
516				if (next.length() > 0) {
517					status_t nextError = walk_integrity_sequence(device, blockSize, blockShift,
518					                                             next, sequenceNumber+1);
519					if (nextError && nextError != B_ENTRY_NOT_FOUND) {
520						// Continuation proved invalid
521						error = nextError;
522						break;
523					} else {
524						// Either the continuation was valid or empty; either way,
525						// we're done searching.
526						break;
527					}
528				}
529			} else {
530				PDUMP(tag);
531			}
532		}
533		// If we hit an error on the first item, consider the extent empty,
534		// otherwise just break out of the loop and assume part of the
535		// extent is unrecorded
536		if (loopError) {
537			if (i == 0)
538				error = B_ENTRY_NOT_FOUND;
539			else
540				break;
541		}
542	}
543	if (!error)
544		error = lastDescriptorWasClosed ? B_OK : B_BAD_DATA;
545	if (!error)
546		error = highestMinimumUDFReadRevision <= UDF_MAX_READ_REVISION ? B_OK : B_ERROR;
547	RETURN(error);
548}
549
550