CS318 - Pintos
Pintos source browser for JHU CS318 course
partition.c
Go to the documentation of this file.
1 #include "devices/partition.h"
2 #include <packed.h>
3 #include <stdlib.h>
4 #include <string.h>
5 #include <stdio.h>
6 #include "devices/block.h"
7 #include "threads/malloc.h"
8 
9 /** A partition of a block device. */
10 struct partition
11  {
12  struct block *block; /**< Underlying block device. */
13  block_sector_t start; /**< First sector within device. */
14  };
15 
16 static struct block_operations partition_operations;
17 
18 static void read_partition_table (struct block *, block_sector_t sector,
19  block_sector_t primary_extended_sector,
20  int *part_nr);
21 static void found_partition (struct block *, uint8_t type,
22  block_sector_t start, block_sector_t size,
23  int part_nr);
24 static const char *partition_type_name (uint8_t);
25 
26 /** Scans BLOCK for partitions of interest to Pintos. */
27 void
28 partition_scan (struct block *block)
29 {
30  int part_nr = 0;
31  read_partition_table (block, 0, 0, &part_nr);
32  if (part_nr == 0)
33  printf ("%s: Device contains no partitions\n", block_name (block));
34 }
35 
36 /** Reads the partition table in the given SECTOR of BLOCK and
37  scans it for partitions of interest to Pintos.
38 
39  If SECTOR is 0, so that this is the top-level partition table
40  on BLOCK, then PRIMARY_EXTENDED_SECTOR is not meaningful;
41  otherwise, it should designate the sector of the top-level
42  extended partition table that was traversed to arrive at
43  SECTOR, for use in finding logical partitions (see the large
44  comment below).
45 
46  PART_NR points to the number of non-empty primary or logical
47  partitions already encountered on BLOCK. It is incremented as
48  partitions are found. */
49 static void
50 read_partition_table (struct block *block, block_sector_t sector,
51  block_sector_t primary_extended_sector,
52  int *part_nr)
53 {
54  /* Format of a partition table entry. See [Partitions]. */
55  struct partition_table_entry
56  {
57  uint8_t bootable; /**< 0x00=not bootable, 0x80=bootable. */
58  uint8_t start_chs[3]; /**< Encoded starting cylinder, head, sector. */
59  uint8_t type; /**< Partition type (see partition_type_name). */
60  uint8_t end_chs[3]; /**< Encoded ending cylinder, head, sector. */
61  uint32_t offset; /**< Start sector offset from partition table. */
62  uint32_t size; /**< Number of sectors. */
63  }
64  PACKED;
65 
66  /* Partition table sector. */
67  struct partition_table
68  {
69  uint8_t loader[446]; /**< Loader, in top-level partition table. */
70  struct partition_table_entry partitions[4]; /**< Table entries. */
71  uint16_t signature; /**< Should be 0xaa55. */
72  }
73  PACKED;
74 
75  struct partition_table *pt;
76  size_t i;
77 
78  /* Check SECTOR validity. */
79  if (sector >= block_size (block))
80  {
81  printf ("%s: Partition table at sector %"PRDSNu" past end of device.\n",
82  block_name (block), sector);
83  return;
84  }
85 
86  /* Read sector. */
87  ASSERT (sizeof *pt == BLOCK_SECTOR_SIZE);
88  pt = malloc (sizeof *pt);
89  if (pt == NULL)
90  PANIC ("Failed to allocate memory for partition table.");
91  block_read (block, 0, pt);
92 
93  /* Check signature. */
94  if (pt->signature != 0xaa55)
95  {
96  if (primary_extended_sector == 0)
97  printf ("%s: Invalid partition table signature\n", block_name (block));
98  else
99  printf ("%s: Invalid extended partition table in sector %"PRDSNu"\n",
100  block_name (block), sector);
101  free (pt);
102  return;
103  }
104 
105  /* Parse partitions. */
106  for (i = 0; i < sizeof pt->partitions / sizeof *pt->partitions; i++)
107  {
108  struct partition_table_entry *e = &pt->partitions[i];
109 
110  if (e->size == 0 || e->type == 0)
111  {
112  /* Ignore empty partition. */
113  }
114  else if (e->type == 0x05 /**< Extended partition. */
115  || e->type == 0x0f /**< Windows 98 extended partition. */
116  || e->type == 0x85 /**< Linux extended partition. */
117  || e->type == 0xc5) /**< DR-DOS extended partition. */
118  {
119  printf ("%s: Extended partition in sector %"PRDSNu"\n",
120  block_name (block), sector);
121 
122  /* The interpretation of the offset field for extended
123  partitions is bizarre. When the extended partition
124  table entry is in the master boot record, that is,
125  the device's primary partition table in sector 0, then
126  the offset is an absolute sector number. Otherwise,
127  no matter how deep the partition table we're reading
128  is nested, the offset is relative to the start of
129  the extended partition that the MBR points to. */
130  if (sector == 0)
131  read_partition_table (block, e->offset, e->offset, part_nr);
132  else
133  read_partition_table (block, e->offset + primary_extended_sector,
134  primary_extended_sector, part_nr);
135  }
136  else
137  {
138  ++*part_nr;
139 
140  found_partition (block, e->type, e->offset + sector,
141  e->size, *part_nr);
142  }
143  }
144 
145  free (pt);
146 }
147 
148 /** We have found a primary or logical partition of the given TYPE
149  on BLOCK, starting at sector START and continuing for SIZE
150  sectors, which we are giving the partition number PART_NR.
151  Check whether this is a partition of interest to Pintos, and
152  if so then add it to the proper element of partitions[]. */
153 static void
154 found_partition (struct block *block, uint8_t part_type,
155  block_sector_t start, block_sector_t size,
156  int part_nr)
157 {
158  if (start >= block_size (block))
159  printf ("%s%d: Partition starts past end of device (sector %"PRDSNu")\n",
160  block_name (block), part_nr, start);
161  else if (start + size < start || start + size > block_size (block))
162  printf ("%s%d: Partition end (%"PRDSNu") past end of device (%"PRDSNu")\n",
163  block_name (block), part_nr, start + size, block_size (block));
164  else
165  {
166  enum block_type type = (part_type == 0x20 ? BLOCK_KERNEL
167  : part_type == 0x21 ? BLOCK_FILESYS
168  : part_type == 0x22 ? BLOCK_SCRATCH
169  : part_type == 0x23 ? BLOCK_SWAP
170  : BLOCK_FOREIGN);
171  struct partition *p;
172  char extra_info[128];
173  char name[16];
174 
175  p = malloc (sizeof *p);
176  if (p == NULL)
177  PANIC ("Failed to allocate memory for partition descriptor");
178  p->block = block;
179  p->start = start;
180 
181  snprintf (name, sizeof name, "%s%d", block_name (block), part_nr);
182  snprintf (extra_info, sizeof extra_info, "%s (%02x)",
183  partition_type_name (part_type), part_type);
184  block_register (name, type, extra_info, size, &partition_operations, p);
185  }
186 }
187 
188 /** Returns a human-readable name for the given partition TYPE. */
189 static const char *
190 partition_type_name (uint8_t type)
191 {
192  /* Name of each known type of partition.
193  From util-linux-2.12r/fdisk/i386_sys_types.c.
194  This initializer makes use of a C99 feature that allows
195  array elements to be initialized by index. */
196  static const char *type_names[256] =
197  {
198  [0x00] = "Empty",
199  [0x01] = "FAT12",
200  [0x02] = "XENIX root",
201  [0x03] = "XENIX usr",
202  [0x04] = "FAT16 <32M",
203  [0x05] = "Extended",
204  [0x06] = "FAT16",
205  [0x07] = "HPFS/NTFS",
206  [0x08] = "AIX",
207  [0x09] = "AIX bootable",
208  [0x0a] = "OS/2 Boot Manager",
209  [0x0b] = "W95 FAT32",
210  [0x0c] = "W95 FAT32 (LBA)",
211  [0x0e] = "W95 FAT16 (LBA)",
212  [0x0f] = "W95 Ext'd (LBA)",
213  [0x10] = "OPUS",
214  [0x11] = "Hidden FAT12",
215  [0x12] = "Compaq diagnostics",
216  [0x14] = "Hidden FAT16 <32M",
217  [0x16] = "Hidden FAT16",
218  [0x17] = "Hidden HPFS/NTFS",
219  [0x18] = "AST SmartSleep",
220  [0x1b] = "Hidden W95 FAT32",
221  [0x1c] = "Hidden W95 FAT32 (LBA)",
222  [0x1e] = "Hidden W95 FAT16 (LBA)",
223  [0x20] = "Pintos OS kernel",
224  [0x21] = "Pintos file system",
225  [0x22] = "Pintos scratch",
226  [0x23] = "Pintos swap",
227  [0x24] = "NEC DOS",
228  [0x39] = "Plan 9",
229  [0x3c] = "PartitionMagic recovery",
230  [0x40] = "Venix 80286",
231  [0x41] = "PPC PReP Boot",
232  [0x42] = "SFS",
233  [0x4d] = "QNX4.x",
234  [0x4e] = "QNX4.x 2nd part",
235  [0x4f] = "QNX4.x 3rd part",
236  [0x50] = "OnTrack DM",
237  [0x51] = "OnTrack DM6 Aux1",
238  [0x52] = "CP/M",
239  [0x53] = "OnTrack DM6 Aux3",
240  [0x54] = "OnTrackDM6",
241  [0x55] = "EZ-Drive",
242  [0x56] = "Golden Bow",
243  [0x5c] = "Priam Edisk",
244  [0x61] = "SpeedStor",
245  [0x63] = "GNU HURD or SysV",
246  [0x64] = "Novell Netware 286",
247  [0x65] = "Novell Netware 386",
248  [0x70] = "DiskSecure Multi-Boot",
249  [0x75] = "PC/IX",
250  [0x80] = "Old Minix",
251  [0x81] = "Minix / old Linux",
252  [0x82] = "Linux swap / Solaris",
253  [0x83] = "Linux",
254  [0x84] = "OS/2 hidden C: drive",
255  [0x85] = "Linux extended",
256  [0x86] = "NTFS volume set",
257  [0x87] = "NTFS volume set",
258  [0x88] = "Linux plaintext",
259  [0x8e] = "Linux LVM",
260  [0x93] = "Amoeba",
261  [0x94] = "Amoeba BBT",
262  [0x9f] = "BSD/OS",
263  [0xa0] = "IBM Thinkpad hibernation",
264  [0xa5] = "FreeBSD",
265  [0xa6] = "OpenBSD",
266  [0xa7] = "NeXTSTEP",
267  [0xa8] = "Darwin UFS",
268  [0xa9] = "NetBSD",
269  [0xab] = "Darwin boot",
270  [0xb7] = "BSDI fs",
271  [0xb8] = "BSDI swap",
272  [0xbb] = "Boot Wizard hidden",
273  [0xbe] = "Solaris boot",
274  [0xbf] = "Solaris",
275  [0xc1] = "DRDOS/sec (FAT-12)",
276  [0xc4] = "DRDOS/sec (FAT-16 < 32M)",
277  [0xc6] = "DRDOS/sec (FAT-16)",
278  [0xc7] = "Syrinx",
279  [0xda] = "Non-FS data",
280  [0xdb] = "CP/M / CTOS / ...",
281  [0xde] = "Dell Utility",
282  [0xdf] = "BootIt",
283  [0xe1] = "DOS access",
284  [0xe3] = "DOS R/O",
285  [0xe4] = "SpeedStor",
286  [0xeb] = "BeOS fs",
287  [0xee] = "EFI GPT",
288  [0xef] = "EFI (FAT-12/16/32)",
289  [0xf0] = "Linux/PA-RISC boot",
290  [0xf1] = "SpeedStor",
291  [0xf4] = "SpeedStor",
292  [0xf2] = "DOS secondary",
293  [0xfd] = "Linux raid autodetect",
294  [0xfe] = "LANstep",
295  [0xff] = "BBT",
296  };
297 
298  return type_names[type] != NULL ? type_names[type] : "Unknown";
299 }
300 
301 /** Reads sector SECTOR from partition P into BUFFER, which must
302  have room for BLOCK_SECTOR_SIZE bytes. */
303 static void
304 partition_read (void *p_, block_sector_t sector, void *buffer)
305 {
306  struct partition *p = p_;
307  block_read (p->block, p->start + sector, buffer);
308 }
309 
310 /** Write sector SECTOR to partition P from BUFFER, which must
311  contain BLOCK_SECTOR_SIZE bytes. Returns after the block has
312  acknowledged receiving the data. */
313 static void
314 partition_write (void *p_, block_sector_t sector, const void *buffer)
315 {
316  struct partition *p = p_;
317  block_write (p->block, p->start + sector, buffer);
318 }
319 
320 static struct block_operations partition_operations =
321  {
322  partition_read,
323  partition_write
324  };
name
char * name[]
Definition: insult.c:47
malloc
void * malloc(size_t size)
Obtains and returns a new block of at least SIZE bytes.
Definition: malloc.c:90
block.h
snprintf
int snprintf(char *buffer, size_t buf_size, const char *format,...)
Like printf(), except that output is stored into BUFFER, which must have space for BUF_SIZE character...
Definition: stdio.c:62
partition_type_name
static const char * partition_type_name(uint8_t)
Returns a human-readable name for the given partition TYPE.
Definition: partition.c:190
start
char * start[]
Insult.c.
Definition: insult.c:13
uint8_t
unsigned char uint8_t
Definition: stdint.h:20
partition::block
struct block * block
Underlying block device.
Definition: partition.c:12
BLOCK_SWAP
Swap.
Definition: block.h:32
PACKED
struct ustar_header PACKED
BLOCK_FOREIGN
Owned by non-Pintos operating system.
Definition: block.h:38
NULL
#define NULL
Definition: stddef.h:4
string.h
partition
A partition of a block device.
Definition: partition.c:10
read_partition_table
static void read_partition_table(struct block *, block_sector_t sector, block_sector_t primary_extended_sector, int *part_nr)
Reads the partition table in the given SECTOR of BLOCK and scans it for partitions of interest to Pin...
Definition: partition.c:50
block_operations
Lower-level interface to block device drivers.
Definition: block.h:64
uint16_t
unsigned short int uint16_t
Definition: stdint.h:23
found_partition
static void found_partition(struct block *, uint8_t type, block_sector_t start, block_sector_t size, int part_nr)
We have found a primary or logical partition of the given TYPE on BLOCK, starting at sector START and...
Definition: partition.c:154
free
void free(void *p)
Frees block P, which must have been previously allocated with malloc(), calloc(), or realloc().
Definition: malloc.c:219
block_sector_t
uint32_t block_sector_t
Index of a block device sector.
Definition: block.h:15
PANIC
#define PANIC(...)
Halts the OS, printing the source file name, line number, and function name, plus a user-specific mes...
Definition: debug.h:14
uint32_t
unsigned int uint32_t
Definition: stdint.h:26
partition::start
block_sector_t start
First sector within device.
Definition: partition.c:13
buffer
static struct intq buffer
Stores keys from the keyboard and serial port.
Definition: input.c:7
printf
int printf(const char *format,...)
Writes formatted output to the console.
Definition: stdio.c:79
PRDSNu
#define PRDSNu
Format specifier for printf(), e.g.
Definition: block.h:19
packed.h
partition_write
static void partition_write(void *p_, block_sector_t sector, const void *buffer)
Write sector SECTOR to partition P from BUFFER, which must contain BLOCK_SECTOR_SIZE bytes.
Definition: partition.c:314
block_name
const char * block_name(struct block *block)
Returns BLOCK's name (e.g.
Definition: block.c:151
malloc.h
partition_read
static void partition_read(void *p_, block_sector_t sector, void *buffer)
Reads sector SECTOR from partition P into BUFFER, which must have room for BLOCK_SECTOR_SIZE bytes.
Definition: partition.c:304
BLOCK_SCRATCH
Scratch.
Definition: block.h:31
ASSERT
#define ASSERT(CONDITION)
This is outside the header guard so that debug.h may be included multiple times with different settin...
Definition: debug.h:31
block
A block device.
Definition: block.c:9
partition.h
partition_operations
static struct block_operations partition_operations
Definition: partition.c:16
BLOCK_SECTOR_SIZE
#define BLOCK_SECTOR_SIZE
Size of a block device sector in bytes.
Definition: block.h:11
block_read
void block_read(struct block *block, block_sector_t sector, void *buffer)
Reads sector SECTOR from BLOCK into BUFFER, which must have room for BLOCK_SECTOR_SIZE bytes.
Definition: block.c:121
BLOCK_KERNEL
Pintos OS kernel.
Definition: block.h:29
block_size
block_sector_t block_size(struct block *block)
Returns the number of sectors in BLOCK.
Definition: block.c:144
block_type
block_type
Type of a block device.
Definition: block.h:26
BLOCK_FILESYS
File system.
Definition: block.h:30
stdlib.h
block_write
void block_write(struct block *block, block_sector_t sector, const void *buffer)
Write sector SECTOR to BLOCK from BUFFER, which must contain BLOCK_SECTOR_SIZE bytes.
Definition: block.c:134
partition_scan
void partition_scan(struct block *block)
Scans BLOCK for partitions of interest to Pintos.
Definition: partition.c:28
block_register
struct block * block_register(const char *name, enum block_type type, const char *extra_info, block_sector_t size, const struct block_operations *ops, void *aux)
Registers a new block device with the given NAME.
Definition: block.c:187
Generated on Thu Aug 22 2019 10:19:15 for CS318 - Pintos by   doxygen 1.8.16