Imported Upstream version 0.6.3
[platform/upstream/multipath-tools.git] / kpartx / gpt.c
1 /*
2     gpt.[ch]
3
4     Copyright (C) 2000-2001 Dell Computer Corporation <Matt_Domsch@dell.com>
5
6     EFI GUID Partition Table handling
7     Per Intel EFI Specification v1.02
8     http://developer.intel.com/technology/efi/efi.htm
9
10     This program is free software; you can redistribute it and/or modify
11     it under the terms of the GNU General Public License as published by
12     the Free Software Foundation; either version 2 of the License, or
13     (at your option) any later version.
14
15     This program is distributed in the hope that it will be useful,
16     but WITHOUT ANY WARRANTY; without even the implied warranty of
17     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18     GNU General Public License for more details.
19
20     You should have received a copy of the GNU General Public License
21     along with this program.  If not, see <http://www.gnu.org/licenses/>.
22 */
23
24 #define _FILE_OFFSET_BITS 64
25
26 #include "gpt.h"
27 #include <stdio.h>
28 #include <string.h>
29 #include <stdlib.h>
30 #include <inttypes.h>
31 #include <sys/stat.h>
32 #include <sys/ioctl.h>
33 #include <fcntl.h>
34 #include <unistd.h>
35 #include <errno.h>
36 #include <endian.h>
37 #include <byteswap.h>
38 #include <linux/fs.h>
39 #include "crc32.h"
40 #include "kpartx.h"
41
42 #if BYTE_ORDER == LITTLE_ENDIAN
43 #  define __le16_to_cpu(x) (x)
44 #  define __le32_to_cpu(x) (x)
45 #  define __le64_to_cpu(x) (x)
46 #  define __cpu_to_le32(x) (x)
47 #elif BYTE_ORDER == BIG_ENDIAN
48 #  define __le16_to_cpu(x) bswap_16(x)
49 #  define __le32_to_cpu(x) bswap_32(x)
50 #  define __le64_to_cpu(x) bswap_64(x)
51 #  define __cpu_to_le32(x) bswap_32(x)
52 #endif
53
54 #ifndef BLKGETLASTSECT
55 #define BLKGETLASTSECT  _IO(0x12,108)   /* get last sector of block device */
56 #endif
57 #ifndef BLKGETSIZE
58 #define BLKGETSIZE _IO(0x12,96)         /* return device size */
59 #endif
60 #ifndef BLKSSZGET
61 #define BLKSSZGET  _IO(0x12,104)        /* get block device sector size */
62 #endif
63 #ifndef BLKGETSIZE64
64 #define BLKGETSIZE64 _IOR(0x12,114,sizeof(uint64_t))    /* return device size in bytes (u64 *arg) */
65 #endif
66
67 struct blkdev_ioctl_param {
68         unsigned int block;
69         size_t content_length;
70         char * block_contents;
71 };
72
73 /**
74  * efi_crc32() - EFI version of crc32 function
75  * @buf: buffer to calculate crc32 of
76  * @len - length of buf
77  *
78  * Description: Returns EFI-style CRC32 value for @buf
79  *
80  * This function uses the little endian Ethernet polynomial
81  * but seeds the function with ~0, and xor's with ~0 at the end.
82  * Note, the EFI Specification, v1.02, has a reference to
83  * Dr. Dobbs Journal, May 1994 (actually it's in May 1992).
84  */
85 static inline uint32_t
86 efi_crc32(const void *buf, unsigned long len)
87 {
88         return (crc32(~0L, buf, len) ^ ~0L);
89 }
90
91 /**
92  * is_pmbr_valid(): test Protective MBR for validity
93  * @mbr: pointer to a legacy mbr structure
94  *
95  * Description: Returns 1 if PMBR is valid, 0 otherwise.
96  * Validity depends on two things:
97  *  1) MSDOS signature is in the last two bytes of the MBR
98  *  2) One partition of type 0xEE is found
99  */
100 static int
101 is_pmbr_valid(legacy_mbr *mbr)
102 {
103         int i, found = 0, signature = 0;
104         if (!mbr)
105                 return 0;
106         signature = (__le16_to_cpu(mbr->signature) == MSDOS_MBR_SIGNATURE);
107         for (i = 0; signature && i < 4; i++) {
108                 if (mbr->partition[i].sys_type ==
109                     EFI_PMBR_OSTYPE_EFI_GPT) {
110                         found = 1;
111                         break;
112                 }
113         }
114         return (signature && found);
115 }
116
117
118 /************************************************************
119  * _get_num_sectors
120  * Requires:
121  *  - filedes is an open file descriptor, suitable for reading
122  * Modifies: nothing
123  * Returns:
124  *  Last LBA value on success
125  *  0 on error
126  *
127  * Try getting BLKGETSIZE64 and BLKSSZGET first,
128  * then BLKGETSIZE if necessary.
129  *  Kernels 2.4.15-2.4.18 and 2.5.0-2.5.3 have a broken BLKGETSIZE64
130  *  which returns the number of 512-byte sectors, not the size of
131  *  the disk in bytes. Fixed in kernels 2.4.18-pre8 and 2.5.4-pre3.
132  ************************************************************/
133 static uint64_t
134 _get_num_sectors(int filedes)
135 {
136         int rc;
137         uint64_t bytes=0;
138
139         rc = ioctl(filedes, BLKGETSIZE64, &bytes);
140         if (!rc)
141                 return bytes / get_sector_size(filedes);
142
143         return 0;
144 }
145
146 /************************************************************
147  * last_lba(): return number of last logical block of device
148  *
149  * @fd
150  *
151  * Description: returns Last LBA value on success, 0 on error.
152  * Notes: The value st_blocks gives the size of the file
153  *        in 512-byte blocks, which is OK if
154  *        EFI_BLOCK_SIZE_SHIFT == 9.
155  ************************************************************/
156
157 static uint64_t
158 last_lba(int filedes)
159 {
160         int rc;
161         uint64_t sectors = 0;
162         struct stat s;
163         memset(&s, 0, sizeof (s));
164         rc = fstat(filedes, &s);
165         if (rc == -1) {
166                 fprintf(stderr, "last_lba() could not stat: %s\n",
167                         strerror(errno));
168                 return 0;
169         }
170
171         if (S_ISBLK(s.st_mode)) {
172                 sectors = _get_num_sectors(filedes);
173         } else {
174                 fprintf(stderr,
175                         "last_lba(): I don't know how to handle files with mode %x\n",
176                         s.st_mode);
177                 sectors = 1;
178         }
179
180         return sectors ? sectors - 1 : 0;
181 }
182
183
184 static ssize_t
185 read_lastoddsector(int fd, uint64_t lba, void *buffer, size_t count)
186 {
187         int rc;
188         struct blkdev_ioctl_param ioctl_param;
189
190         if (!buffer) return 0;
191
192         ioctl_param.block = 0; /* read the last sector */
193         ioctl_param.content_length = count;
194         ioctl_param.block_contents = buffer;
195
196         rc = ioctl(fd, BLKGETLASTSECT, &ioctl_param);
197         if (rc == -1) perror("read failed");
198
199         return !rc;
200 }
201
202 static ssize_t
203 read_lba(int fd, uint64_t lba, void *buffer, size_t bytes)
204 {
205         int sector_size = get_sector_size(fd);
206         off_t offset = lba * sector_size;
207         uint64_t lastlba;
208         ssize_t bytesread;
209
210         if (lseek(fd, offset, SEEK_SET) < 0)
211                 return 0;
212         bytesread = read(fd, buffer, bytes);
213
214         lastlba = last_lba(fd);
215         if (!lastlba)
216                 return bytesread;
217
218         /* Kludge.  This is necessary to read/write the last
219            block of an odd-sized disk, until Linux 2.5.x kernel fixes.
220            This is only used by gpt.c, and only to read
221            one sector, so we don't have to be fancy.
222         */
223         if (!bytesread && !(lastlba & 1) && lba == lastlba) {
224                 bytesread = read_lastoddsector(fd, lba, buffer, bytes);
225         }
226         return bytesread;
227 }
228
229 /**
230  * alloc_read_gpt_entries(): reads partition entries from disk
231  * @fd  is an open file descriptor to the whole disk
232  * @gpt is a buffer into which the GPT will be put
233  * Description: Returns ptes on success,  NULL on error.
234  * Allocates space for PTEs based on information found in @gpt.
235  * Notes: remember to free pte when you're done!
236  */
237 static gpt_entry *
238 alloc_read_gpt_entries(int fd, gpt_header * gpt)
239 {
240         gpt_entry *pte;
241         size_t count = __le32_to_cpu(gpt->num_partition_entries) *
242                 __le32_to_cpu(gpt->sizeof_partition_entry);
243
244         if (!count) return NULL;
245
246         pte = (gpt_entry *)malloc(count);
247         if (!pte)
248                 return NULL;
249         memset(pte, 0, count);
250
251         if (!read_lba(fd, __le64_to_cpu(gpt->partition_entry_lba), pte,
252                       count)) {
253                 free(pte);
254                 return NULL;
255         }
256         return pte;
257 }
258
259 /**
260  * alloc_read_gpt_header(): Allocates GPT header, reads into it from disk
261  * @fd  is an open file descriptor to the whole disk
262  * @lba is the Logical Block Address of the partition table
263  *
264  * Description: returns GPT header on success, NULL on error.   Allocates
265  * and fills a GPT header starting at @ from @bdev.
266  * Note: remember to free gpt when finished with it.
267  */
268 static gpt_header *
269 alloc_read_gpt_header(int fd, uint64_t lba)
270 {
271         gpt_header *gpt;
272         gpt = (gpt_header *)
273             malloc(sizeof (gpt_header));
274         if (!gpt)
275                 return NULL;
276         memset(gpt, 0, sizeof (*gpt));
277         if (!read_lba(fd, lba, gpt, sizeof (gpt_header))) {
278                 free(gpt);
279                 return NULL;
280         }
281
282         return gpt;
283 }
284
285 /**
286  * is_gpt_valid() - tests one GPT header and PTEs for validity
287  * @fd  is an open file descriptor to the whole disk
288  * @lba is the logical block address of the GPT header to test
289  * @gpt is a GPT header ptr, filled on return.
290  * @ptes is a PTEs ptr, filled on return.
291  *
292  * Description: returns 1 if valid,  0 on error.
293  * If valid, returns pointers to newly allocated GPT header and PTEs.
294  */
295 static int
296 is_gpt_valid(int fd, uint64_t lba,
297              gpt_header ** gpt, gpt_entry ** ptes)
298 {
299         int rc = 0;             /* default to not valid */
300         uint32_t crc, origcrc;
301
302         if (!gpt || !ptes)
303                 return 0;
304         if (!(*gpt = alloc_read_gpt_header(fd, lba)))
305                 return 0;
306
307         /* Check the GUID Partition Table signature */
308         if (__le64_to_cpu((*gpt)->signature) != GPT_HEADER_SIGNATURE) {
309                 /*
310                    printf("GUID Partition Table Header signature is wrong: %" PRIx64" != %" PRIx64 "\n",
311                    __le64_to_cpu((*gpt)->signature), GUID_PT_HEADER_SIGNATURE);
312                  */
313                 free(*gpt);
314                 *gpt = NULL;
315                 return rc;
316         }
317
318         /* Check the GUID Partition Table Header CRC */
319         origcrc = __le32_to_cpu((*gpt)->header_crc32);
320         (*gpt)->header_crc32 = 0;
321         crc = efi_crc32(*gpt, __le32_to_cpu((*gpt)->header_size));
322         if (crc != origcrc) {
323                 // printf( "GPTH CRC check failed, %x != %x.\n", origcrc, crc);
324                 (*gpt)->header_crc32 = __cpu_to_le32(origcrc);
325                 free(*gpt);
326                 *gpt = NULL;
327                 return 0;
328         }
329         (*gpt)->header_crc32 = __cpu_to_le32(origcrc);
330
331         /* Check that the my_lba entry points to the LBA
332          * that contains the GPT we read */
333         if (__le64_to_cpu((*gpt)->my_lba) != lba) {
334                 /*
335                 printf( "my_lba % PRIx64 "x != lba %"PRIx64 "x.\n",
336                                 __le64_to_cpu((*gpt)->my_lba), lba);
337                  */
338                 free(*gpt);
339                 *gpt = NULL;
340                 return 0;
341         }
342
343         /* Check that sizeof_partition_entry has the correct value */
344         if (__le32_to_cpu((*gpt)->sizeof_partition_entry) != sizeof(gpt_entry)) {
345                 // printf("GUID partition entry size check failed.\n");
346                 free(*gpt);
347                 *gpt = NULL;
348                 return 0;
349         }
350
351
352         /* Check that sizeof_partition_entry has the correct value */
353         if (__le32_to_cpu((*gpt)->sizeof_partition_entry) != sizeof(gpt_entry)) {
354                 // printf("GUID partition entry size check failed.\n");
355                 free(*gpt);
356                 *gpt = NULL;
357                 return 0;
358         }
359
360
361         if (!(*ptes = alloc_read_gpt_entries(fd, *gpt))) {
362                 free(*gpt);
363                 *gpt = NULL;
364                 return 0;
365         }
366
367         /* Check the GUID Partition Entry Array CRC */
368         crc = efi_crc32(*ptes,
369                         __le32_to_cpu((*gpt)->num_partition_entries) *
370                         __le32_to_cpu((*gpt)->sizeof_partition_entry));
371         if (crc != __le32_to_cpu((*gpt)->partition_entry_array_crc32)) {
372                 // printf("GUID Partitition Entry Array CRC check failed.\n");
373                 free(*gpt);
374                 *gpt = NULL;
375                 free(*ptes);
376                 *ptes = NULL;
377                 return 0;
378         }
379
380         /* We're done, all's well */
381         return 1;
382 }
383 /**
384  * compare_gpts() - Search disk for valid GPT headers and PTEs
385  * @pgpt is the primary GPT header
386  * @agpt is the alternate GPT header
387  * @lastlba is the last LBA number
388  * Description: Returns nothing.  Sanity checks pgpt and agpt fields
389  * and prints warnings on discrepancies.
390  *
391  */
392 static void
393 compare_gpts(gpt_header *pgpt, gpt_header *agpt, uint64_t lastlba)
394 {
395         int error_found = 0;
396         if (!pgpt || !agpt)
397                 return;
398         if (__le64_to_cpu(pgpt->my_lba) != __le64_to_cpu(agpt->alternate_lba)) {
399                 error_found++;
400                 fprintf(stderr,
401                        "GPT:Primary header LBA != Alt. header alternate_lba\n");
402 #ifdef DEBUG
403                 fprintf(stderr,  "GPT:%" PRIx64 " != %" PRIx64 "\n",
404                        __le64_to_cpu(pgpt->my_lba),
405                        __le64_to_cpu(agpt->alternate_lba));
406 #endif
407         }
408         if (__le64_to_cpu(pgpt->alternate_lba) != __le64_to_cpu(agpt->my_lba)) {
409                 error_found++;
410                 fprintf(stderr,
411                        "GPT:Primary header alternate_lba != Alt. header my_lba\n");
412 #ifdef DEBUG
413                 fprintf(stderr,  "GPT:%" PRIx64 " != %" PRIx64 "\n",
414                        __le64_to_cpu(pgpt->alternate_lba),
415                        __le64_to_cpu(agpt->my_lba));
416 #endif
417         }
418         if (__le64_to_cpu(pgpt->first_usable_lba) !=
419             __le64_to_cpu(agpt->first_usable_lba)) {
420                 error_found++;
421                 fprintf(stderr,  "GPT:first_usable_lbas don't match.\n");
422 #ifdef DEBUG
423                 fprintf(stderr,  "GPT:%" PRIx64 " != %" PRIx64 "\n",
424                        __le64_to_cpu(pgpt->first_usable_lba),
425                        __le64_to_cpu(agpt->first_usable_lba));
426 #endif
427         }
428         if (__le64_to_cpu(pgpt->last_usable_lba) !=
429             __le64_to_cpu(agpt->last_usable_lba)) {
430                 error_found++;
431                 fprintf(stderr,  "GPT:last_usable_lbas don't match.\n");
432 #ifdef DEBUG
433                 fprintf(stderr,  "GPT:%" PRIx64 " != %" PRIx64 "\n",
434                        __le64_to_cpu(pgpt->last_usable_lba),
435                        __le64_to_cpu(agpt->last_usable_lba));
436 #endif
437         }
438         if (efi_guidcmp(pgpt->disk_guid, agpt->disk_guid)) {
439                 error_found++;
440                 fprintf(stderr,  "GPT:disk_guids don't match.\n");
441         }
442         if (__le32_to_cpu(pgpt->num_partition_entries) !=
443             __le32_to_cpu(agpt->num_partition_entries)) {
444                 error_found++;
445                 fprintf(stderr,  "GPT:num_partition_entries don't match: "
446                        "0x%x != 0x%x\n",
447                        __le32_to_cpu(pgpt->num_partition_entries),
448                        __le32_to_cpu(agpt->num_partition_entries));
449         }
450         if (__le32_to_cpu(pgpt->sizeof_partition_entry) !=
451             __le32_to_cpu(agpt->sizeof_partition_entry)) {
452                 error_found++;
453                 fprintf(stderr,
454                        "GPT:sizeof_partition_entry values don't match: "
455                        "0x%x != 0x%x\n",
456                        __le32_to_cpu(pgpt->sizeof_partition_entry),
457                        __le32_to_cpu(agpt->sizeof_partition_entry));
458         }
459         if (__le32_to_cpu(pgpt->partition_entry_array_crc32) !=
460             __le32_to_cpu(agpt->partition_entry_array_crc32)) {
461                 error_found++;
462                 fprintf(stderr,
463                        "GPT:partition_entry_array_crc32 values don't match: "
464                        "0x%x != 0x%x\n",
465                        __le32_to_cpu(pgpt->partition_entry_array_crc32),
466                        __le32_to_cpu(agpt->partition_entry_array_crc32));
467         }
468         if (__le64_to_cpu(pgpt->alternate_lba) != lastlba) {
469                 error_found++;
470                 fprintf(stderr,
471                        "GPT:Primary header thinks Alt. header is not at the end of the disk.\n");
472 #ifdef DEBUG
473                 fprintf(stderr,  "GPT:%" PRIx64 " != %" PRIx64 "\n",
474                        __le64_to_cpu(pgpt->alternate_lba), lastlba);
475 #endif
476         }
477
478         if (__le64_to_cpu(agpt->my_lba) != lastlba) {
479                 error_found++;
480                 fprintf(stderr,
481                        "GPT:Alternate GPT header not at the end of the disk.\n");
482 #ifdef DEBUG
483                 fprintf(stderr,  "GPT:%" PRIx64 " != %" PRIx64 "\n",
484                        __le64_to_cpu(agpt->my_lba), lastlba);
485 #endif
486         }
487
488         if (error_found)
489                 fprintf(stderr,
490                        "GPT: Use GNU Parted to correct GPT errors.\n");
491         return;
492 }
493
494 /**
495  * find_valid_gpt() - Search disk for valid GPT headers and PTEs
496  * @fd  is an open file descriptor to the whole disk
497  * @gpt is a GPT header ptr, filled on return.
498  * @ptes is a PTEs ptr, filled on return.
499  * Description: Returns 1 if valid, 0 on error.
500  * If valid, returns pointers to newly allocated GPT header and PTEs.
501  * Validity depends on finding either the Primary GPT header and PTEs valid,
502  * or the Alternate GPT header and PTEs valid, and the PMBR valid.
503  */
504 static int
505 find_valid_gpt(int fd, gpt_header ** gpt, gpt_entry ** ptes)
506 {
507         extern int force_gpt;
508         int good_pgpt = 0, good_agpt = 0, good_pmbr = 0;
509         gpt_header *pgpt = NULL, *agpt = NULL;
510         gpt_entry *pptes = NULL, *aptes = NULL;
511         legacy_mbr *legacymbr = NULL;
512         uint64_t lastlba;
513         if (!gpt || !ptes)
514                 return 0;
515
516         if (!(lastlba = last_lba(fd)))
517                 return 0;
518         good_pgpt = is_gpt_valid(fd, GPT_PRIMARY_PARTITION_TABLE_LBA,
519                                  &pgpt, &pptes);
520         if (good_pgpt) {
521                 good_agpt = is_gpt_valid(fd,
522                                          __le64_to_cpu(pgpt->alternate_lba),
523                                          &agpt, &aptes);
524                 if (!good_agpt) {
525                         good_agpt = is_gpt_valid(fd, lastlba,
526                                                  &agpt, &aptes);
527                 }
528         }
529         else {
530                 good_agpt = is_gpt_valid(fd, lastlba,
531                                          &agpt, &aptes);
532         }
533
534         /* The obviously unsuccessful case */
535         if (!good_pgpt && !good_agpt) {
536                 goto fail;
537         }
538
539         /* This will be added to the EFI Spec. per Intel after v1.02. */
540         legacymbr = malloc(sizeof (*legacymbr));
541         if (legacymbr) {
542                 memset(legacymbr, 0, sizeof (*legacymbr));
543                 read_lba(fd, 0, (uint8_t *) legacymbr,
544                          sizeof (*legacymbr));
545                 good_pmbr = is_pmbr_valid(legacymbr);
546                 free(legacymbr);
547                 legacymbr=NULL;
548         }
549
550         /* Failure due to bad PMBR */
551         if ((good_pgpt || good_agpt) && !good_pmbr && !force_gpt) {
552                 fprintf(stderr,
553                        "  Warning: Disk has a valid GPT signature "
554                        "but invalid PMBR.\n"
555                        "  Assuming this disk is *not* a GPT disk anymore.\n"
556                        "  Use gpt kernel option to override.  "
557                        "Use GNU Parted to correct disk.\n");
558                 goto fail;
559         }
560
561         /* Would fail due to bad PMBR, but force GPT anyhow */
562         if ((good_pgpt || good_agpt) && !good_pmbr && force_gpt) {
563                 fprintf(stderr,
564                        "  Warning: Disk has a valid GPT signature but "
565                        "invalid PMBR.\n"
566                        "  Use GNU Parted to correct disk.\n"
567                        "  gpt option taken, disk treated as GPT.\n");
568         }
569
570         compare_gpts(pgpt, agpt, lastlba);
571
572         /* The good cases */
573         if (good_pgpt && (good_pmbr || force_gpt)) {
574                 *gpt  = pgpt;
575                 *ptes = pptes;
576                 if (agpt)  { free(agpt);   agpt = NULL; }
577                 if (aptes) { free(aptes); aptes = NULL; }
578                 if (!good_agpt) {
579                         fprintf(stderr,
580                                "Alternate GPT is invalid, "
581                                "using primary GPT.\n");
582                 }
583                 return 1;
584         }
585         else if (good_agpt && (good_pmbr || force_gpt)) {
586                 *gpt  = agpt;
587                 *ptes = aptes;
588                 if (pgpt)  { free(pgpt);   pgpt = NULL; }
589                 if (pptes) { free(pptes); pptes = NULL; }
590                 fprintf(stderr,
591                        "Primary GPT is invalid, using alternate GPT.\n");
592                 return 1;
593         }
594
595 fail:
596         if (pgpt)  { free(pgpt);   pgpt=NULL; }
597         if (agpt)  { free(agpt);   agpt=NULL; }
598         if (pptes) { free(pptes); pptes=NULL; }
599         if (aptes) { free(aptes); aptes=NULL; }
600         *gpt = NULL;
601         *ptes = NULL;
602         return 0;
603 }
604
605 /**
606  * read_gpt_pt()
607  * @fd
608  * @all - slice with start/size of whole disk
609  *
610  *  0 if this isn't our partition table
611  *  number of partitions if successful
612  *
613  */
614 int
615 read_gpt_pt (int fd, struct slice all, struct slice *sp, int ns)
616 {
617         gpt_header *gpt = NULL;
618         gpt_entry *ptes = NULL;
619         uint32_t i;
620         int n = 0;
621         int last_used_index=-1;
622         int sector_size_mul = get_sector_size(fd)/512;
623
624         if (!find_valid_gpt (fd, &gpt, &ptes) || !gpt || !ptes) {
625                 if (gpt)
626                         free (gpt);
627                 if (ptes)
628                         free (ptes);
629                 return 0;
630         }
631
632         for (i = 0; i < __le32_to_cpu(gpt->num_partition_entries) && i < ns; i++) {
633                 if (!efi_guidcmp (NULL_GUID, ptes[i].partition_type_guid)) {
634                         sp[n].start = 0;
635                         sp[n].size = 0;
636                         n++;
637                 } else {
638                         sp[n].start = sector_size_mul *
639                                       __le64_to_cpu(ptes[i].starting_lba);
640                         sp[n].size  = sector_size_mul *
641                                       (__le64_to_cpu(ptes[i].ending_lba) -
642                                        __le64_to_cpu(ptes[i].starting_lba) + 1);
643                         last_used_index=n;
644                         n++;
645                 }
646         }
647         free (ptes);
648         free (gpt);
649         return last_used_index+1;
650 }