Logical block addressing

Last updated

Logical block addressing (LBA) is a common scheme used for specifying the location of blocks of data stored on computer storage devices, generally secondary storage systems such as hard disk drives. LBA is a particularly simple linear addressing scheme; blocks are located by an integer index, with the first block being LBA 0, the second LBA 1, and so on.

Contents

The IDE standard included 22-bit LBA as an option, which was further extended to 28-bit with the release of ATA-1 (1994) and to 48-bit with the release of ATA-6 (2003), whereas the size of entries in on-disk and in-memory data structures holding the address is typically 32 or 64 bits. Most hard disk drives released after 1996 implement logical block addressing.

Overview

In logical block addressing, only one number is used to address data, and each linear base address describes a single block.

The LBA scheme replaces earlier schemes which exposed the physical details of the storage device to the software of the operating system. Chief among these was the cylinder-head-sector (CHS) scheme, where blocks were addressed by means of a tuple which defined the cylinder, head, and sector at which they appeared on the hard disk. CHS did not map well to devices other than hard disks (such as tapes and networked storage), and was generally not used for them. CHS was used in early MFM and RLL drives, and both it and its successor, extended cylinder-head-sector (ECHS), were used in the first ATA drives. However, current disk drives use zone bit recording, where the number of sectors per track depends on the track number. Even though the disk drive will report some CHS values as sectors per track (SPT) and heads per cylinder (HPC), they have little to do with the disk drive's true geometry.

LBA was first introduced in SCSI as an abstraction. While the drive controller still addresses data blocks by their CHS address, this information is generally not used by the SCSI device driver, the OS, filesystem code, or any applications (such as databases) that access the "raw" disk. System calls requiring block-level I/O pass LBA definitions to the storage device driver; for simple cases (where one volume maps to one physical drive), this LBA is then passed directly to the drive controller.

In redundant array of independent disks (RAID) devices and storage area networks (SANs) and where logical drives (logical unit numbers, LUNs) are composed via LUN virtualization and aggregation, LBA addressing of individual disk should be translated by a software layer to provide uniform LBA addressing for the entire storage device.

Enhanced BIOS

The earlier IDE standard from Western Digital introduced 22-bit LBA; in 1994, the ATA-1 standard allowed for 28 bit addresses in both LBA and CHS modes. The CHS scheme used 16 bits for cylinder, 4 bits for head and 8 bits for sector, counting sectors from 1 to 255. This means the reported number of heads never exceeds 16 (0–15), the number of sectors can be 255 (1–255; though 63 is often the largest used) and the number of cylinders can be as large as 65,536 (0–65535), limiting disk size to 128 GiB (≈137.4 GB), assuming 512 byte sectors. These values can be accessed by issuing the ATA command "Identify Device" (ECh) to the drive. [1] :87

However, the IBM BIOS implementation defined in the INT 13h disk access routines used quite a different 24-bit scheme for CHS addressing, with 10 bits for cylinder, 8 bits for head, and 6 bits for sector, or 1024 cylinders, 256 heads, and 63 sectors. [2] This INT 13h implementation had pre-dated the ATA standard, as it was introduced when the IBM PC had only floppy disk storage, and when hard disk drives were introduced on the IBM PC/XT, INT 13h interface could not be practically redesigned due to backward compatibility issues. Overlapping ATA CHS mapping with BIOS CHS mapping produced the lowest common denominator of 10:4:6 bits, or 1024 cylinders, 16 heads, and 63 sectors, which gave the practical limit of 1024×16×63 sectors and 528 MB (504  MiB), assuming 512 byte sectors.

In order for the BIOS to overcome this limit and successfully work with larger hard drives, a CHS translation scheme had to be implemented in the BIOS disk I/O routines which would convert between 24-bit CHS used by INT 13h and 28-bit CHS numbering used by ATA. The translation scheme was called large or bit shift translation. This method would remap 16:4:8 bit ATA cylinders and heads to 10:8:6 bit scheme used by INT 13h, generating much more "virtual" drive heads than the physical disk reported. This increased the practical limit to 1024×256×63 sectors, or 8.4 GB (7.8  GiB).

To further overcome this limit, INT 13h Extensions were introduced with the BIOS Enhanced Disk Drive Services , which removed practical limits on disk size for operating systems which are aware of this new interface, such as the DOS 7.0 component in Windows 95. This enhanced BIOS subsystem supports LBA addressing with LBA or LBA-assisted method, which uses native 28-bit LBA for addressing ATA disks and performs CHS conversion as needed.

The normal or none method reverts to the earlier 10:4:6 bit CHS mode which does not support addressing more than 528 MB.

Installation of Western Digital's OEM-version of EZ Drive, on a 3.5-inch floppy disk. Installation of the Western Digital's EZ Drive, on a 3.5-inch floppy disk.jpg
Installation of Western Digital's OEM-version of EZ Drive, on a 3.5-inch floppy disk.

Until the release of ATA-2 standard in 1996, there were a handful of large hard drives which did not support LBA addressing, so only large or normal methods could be used. However, using the large method also introduced portability problems, as different BIOSes often used different and incompatible translation methods, and hard drives partitioned on a computer with a BIOS from a particular vendor often could not be read on a computer with a different make of BIOS. The solution was to use conversion software such as OnTrack Disk Manager, Micro House EZ-Drive/EZ-BIOS, etc., which installed to the disk's OS loader and replaced INT 13h routines at boot time with custom code. This software could also enable LBA and INT 13h Extensions support for older computers with non LBA-compliant BIOSes.

LBA-assisted translation

When the BIOS is configured to use a disk in LBA-assisted translation mode, the BIOS accesses the hardware using LBA mode, but also presents a translated CHS geometry via the INT 13h interface. The number of cylinders, heads, and sectors in the translated geometry depends on the total size of the disk, as shown in the following table. [3]

Disk sizeSectors/trackHeadsCylinders
1 < X ≤ 504 MiB6316X ÷ (63 × 16 × 512)
504 MiB < X ≤ 1008 MiB6332X ÷ (63 × 32 × 512)
1008 MiB < X ≤ 2016 MiB6364X ÷ (63 × 64 × 512)
2016 MiB < X ≤ 4032 MiB63128X ÷ (63 × 128 × 512)
4032 MiB < X ≤ 8032.5 MiB63255X ÷ (63 × 255 × 512)

LBA48

The current 48-bit LBA scheme was introduced in 2002 with the ATA-6 standard, [4] raising the addressing limit to 248 × 512 bytes, which is exactly 128  PiB or approximately 144  PB. Current PC-compatible computers support INT 13h Extensions, which use 64-bit structures for LBA addressing and should encompass any future extension of LBA addressing, though modern operating systems implement direct disk access and do not use the BIOS subsystems, except at boot load time. However, the common DOS style Master Boot Record (MBR) partition table only supports disk partitions up to 2 TiB in size. For larger partitions this needs to be replaced by another scheme, for instance the GUID Partition Table (GPT) which has the same 64-bit limit as the current INT 13h Extensions.

CHS conversion

LBA and CHS equivalence with 16 heads per cylinder
LBA valueCHS tuple
00, 0, 1
10, 0, 2
20, 0, 3
620, 0, 63
630, 1, 1
9450, 15, 1
10070, 15, 63
10081, 0, 1
10701, 0, 63
10711, 1, 1
11331, 1, 63
11341, 2, 1
20151, 15, 63
20162, 0, 1
16,12715, 15, 63
16,12816, 0, 1
32,25531, 15, 63
32,25632, 0, 1
16,450,55916319, 15, 63
16,514,06316382, 15, 63

In the LBA addressing scheme, sectors are numbered as integer indexes; when mapped to CHS (cylinder-head-sector) tuples, LBA numbering starts with the first cylinder, first head, and track's first sector. Once the track is exhausted, numbering continues to the second head, while staying inside the first cylinder. Once all heads inside the first cylinder are exhausted, numbering continues from the second cylinder, etc. Thus, the lower the LBA value is, the closer the physical sector is to the hard drive's first (that is, outermost [5] ) cylinder.

CHS tuples can be mapped to LBA address with the following formula: [6] [7]

LBA = (C × HPC + H) × SPT + (S − 1)

where

LBA addresses can be mapped to CHS tuples with the following formula ("mod" is the modulo operation, i.e. the remainder, and "÷" is integer division, i.e. the quotient of the division where any fractional part is discarded):

C = LBA ÷ (HPC × SPT)
H = (LBA ÷ SPT) mod HPC
S = (LBA mod SPT) + 1

According to the ATA specifications, "If the content of words (61:60) is greater than or equal to 16,514,064, then the content of word 1 [the number of logical cylinders] shall be equal to 16,383." [1] :20 Therefore, for LBA 16450559, an ATA drive may actually respond with the CHS tuple (16319, 15, 63), and the number of cylinders in this scheme must be much larger than 1024 allowed by INT 13h. [lower-alpha 1]

Operating system dependencies

Operating systems that are sensitive to BIOS-reported drive geometry include Solaris, DOS and Windows NT family, where NTLDR (NT, 2000, XP, Server 2003) or WINLOAD (Vista, Server 2008, Windows 7 and Server 2008 R2) use Master boot record which addresses the disk using CHS; x86-64 and Itanium versions of Windows can partition the drive with GUID Partition Table which uses LBA addressing.

Some operating systems do not require any translation because they do not use geometry reported by BIOS in their boot loaders. Among these operating systems are BSD, Linux, macOS, OS/2 and ReactOS.

See also

Notes

  1. Though CHS addressing definitely uses the mathematical concept of tuple , it may also be considered an example of the general scheme called mixed radix by viewing its cylinders, heads and sectors as having different numerical bases; e.g., cylinders counting from 0 to 1023, heads from 0 to 254 and sectors from 1 to 63.

Related Research Articles

<span class="mw-page-title-main">Parallel ATA</span> Interface standard for the connection of storage devices

Parallel ATA (PATA), originally AT Attachment, also known as IDE, is a standard interface designed for IBM PC-compatible computers. It was first developed by Western Digital and Compaq in 1986 for compatible hard drives and CD or DVD drives. The connection is used for storage devices such as hard disk drives, floppy disk drives, and optical disc drives in computers.

<span class="mw-page-title-main">Disk storage</span> General category of storage mechanisms

Disk storage is a general category of storage mechanisms where data is recorded by various electronic, magnetic, optical, or mechanical changes to a surface layer of one or more rotating disks. A disk drive is a device implementing such a storage mechanism. Notable types are the hard disk drive (HDD) containing a non-removable disk, the floppy disk drive (FDD) and its removable floppy disk, and various optical disc drives (ODD) and associated optical disc media.

<span class="mw-page-title-main">Hard disk drive</span> Electro-mechanical data storage device

A hard disk drive (HDD), hard disk, hard drive, or fixed disk, is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magnetic material. The platters are paired with magnetic heads, usually arranged on a moving actuator arm, which read and write data to the platter surfaces. Data is accessed in a random-access manner, meaning that individual blocks of data can be stored and retrieved in any order. HDDs are a type of non-volatile storage, retaining stored data when powered off. Modern HDDs are typically in the form of a small rectangular box.

<span class="mw-page-title-main">SCSI</span> Set of computer and peripheral connection standards

Small Computer System Interface is a set of standards for physically connecting and transferring data between computers and peripheral devices. The SCSI standards define commands, protocols, electrical, optical and logical interfaces. The SCSI standard defines command sets for specific peripheral device types; the presence of "unknown" as one of these types means that in theory it can be used as an interface to almost any device, but the standard is highly pragmatic and addressed toward commercial requirements. The initial Parallel SCSI was most commonly used for hard disk drives and tape drives, but it can connect a wide range of other devices, including scanners and CD drives, although not all controllers can handle all devices.

File Allocation Table (FAT) is a file system developed for personal computers and was the default filesystem for MS-DOS and Windows 9x operating systems. Originally developed in 1977 for use on floppy disks, it was adapted for use on hard disks and other devices. The increase in disk drives capacity required three major variants: FAT12, FAT16 and FAT32. FAT was replaced with NTFS as the default file system on Microsoft operating systems starting with Windows XP. Nevertheless, FAT continues to be used on flash and other solid-state memory cards and modules, many portable and embedded devices because of its compatibility and ease of implementation.

<span class="mw-page-title-main">Disk partitioning</span> Creation of separate accessible storage areas on a secondary computer storage device

Disk partitioning or disk slicing is the creation of one or more regions on secondary storage, so that each region can be managed separately. These regions are called partitions. It is typically the first step of preparing a newly installed disk, before any file system is created. The disk stores the information about the partitions' locations and sizes in an area known as the partition table that the operating system reads before any other part of the disk. Each partition then appears to the operating system as a distinct "logical" disk that uses part of the actual disk. System administrators use a program called a partition editor to create, resize, delete, and manipulate the partitions. Partitioning allows the use of different filesystems to be installed for different kinds of files. Separating user data from system data can prevent the system partition from becoming full and rendering the system unusable. Partitioning can also make backing up easier. A disadvantage is that it can be difficult to properly size partitions, resulting in having one partition with too much free space and another nearly totally allocated.

Disk formatting is the process of preparing a data storage device such as a hard disk drive, solid-state drive, floppy disk, memory card or USB flash drive for initial use. In some cases, the formatting operation may also create one or more new file systems. The first part of the formatting process that performs basic medium preparation is often referred to as "low-level formatting". Partitioning is the common term for the second part of the process, dividing the device into several sub-devices and, in some cases, writing information to the device allowing an operating system to be booted from it. The third part of the process, usually termed "high-level formatting" most often refers to the process of generating a new file system. In some operating systems all or parts of these three processes can be combined or repeated at different levels and the term "format" is understood to mean an operation in which a new disk medium is fully prepared to store files. Some formatting utilities allow distinguishing between a quick format, which does not erase all existing data and a long option that does erase all existing data.

In computing, an address space defines a range of discrete addresses, each of which may correspond to a network host, peripheral device, disk sector, a memory cell or other logical or physical entity.

<span class="mw-page-title-main">SpinRite</span>

SpinRite is a computer program for scanning magnetic data storage devices such as hard disks, recovering data from them and refreshing their surfaces. The first version was released in 1987 by Steve Gibson. The current version, 6.0, was released in 2004.

<span class="mw-page-title-main">Cylinder-head-sector</span> Historical method for giving addresses to physical data blocks on hard disk drives

Cylinder-head-sector (CHS) is an early method for giving addresses to each physical block of data on a hard disk drive.

<span class="mw-page-title-main">GUID Partition Table</span> Computer disk partitioning standard

The GUID Partition Table (GPT) is a standard for the layout of partition tables of a physical computer storage device, such as a hard disk drive or solid-state drive, using universally unique identifiers, which are also known as globally unique identifiers (GUIDs). Forming a part of the Unified Extensible Firmware Interface (UEFI) standard, it is nevertheless also used for some BIOS systems, because of the limitations of master boot record (MBR) partition tables, which use 32 bits for logical block addressing (LBA) of traditional 512-byte disk sectors.

INT 13h is shorthand for BIOS interrupt call 13hex, the 20th interrupt vector in an x86-based computer system. The BIOS typically sets up a real mode interrupt handler at this vector that provides sector-based hard disk and floppy disk read and write services using cylinder-head-sector (CHS) addressing. Modern PC BIOSes also include INT 13h extension functions, originated by IBM and Microsoft in 1992, that provide those same disk access services using 64-bit LBA addressing; with minor additions, these were quasi-standardized by Phoenix Technologies and others as the EDD BIOS extensions.

The Logical Disk Manager (LDM) is an implementation of a logical volume manager for Microsoft Windows NT, developed by Microsoft and Veritas Software. It was introduced with the Windows 2000 operating system, and is supported in Windows XP, Windows Server 2003, Windows Vista, Windows 7, Windows 8, Windows 10 and Windows 11. The MMC-based Disk Management snap-in hosts the Logical Disk Manager. On Windows 8 and Windows Server 2012, Microsoft deprecated LDM in favor of Storage Spaces.

An extended boot record (EBR), or extended partition boot record (EPBR), is a descriptor for a logical partition under the common DOS disk drive partitioning system. In that system, when one partition record entry in the master boot record (MBR) is designated an extended partition, then that partition can be subdivided into a number of logical partitions. The actual structure of that extended partition is described by one or more EBRs, which are located inside the extended partition. The first EBR will always be located on the very first sector of the extended partition.

A volume boot record (VBR) is a type of boot sector introduced by the IBM Personal Computer. It may be found on a partitioned data storage device, such as a hard disk, or an unpartitioned device, such as a floppy disk, and contains machine code for bootstrapping programs stored in other parts of the device. On non-partitioned storage devices, it is the first sector of the device. On partitioned devices, it is the first sector of an individual partition on the device, with the first sector of the entire device being a Master Boot Record (MBR) containing the partition table.

<span class="mw-page-title-main">Disk sector</span> Logical or physical division of storage media

In computer disk storage, a sector is a subdivision of a track on a magnetic disk or optical disc. Each sector stores a fixed amount of user-accessible data, traditionally 512 bytes for hard disk drives (HDDs) and 2048 bytes for CD-ROMs and DVD-ROMs. Newer HDDs use 4096-byte (4 KiB) sectors, which are known as the Advanced Format (AF).

Fixed-block architecture (FBA) is an IBM term for the hard disk drive (HDD) layout in which each addressable block on the disk has the same size, utilizing 4 byte block numbers and a new set of command codes. FBA as a term was created and used by IBM for its 3310 and 3370 HDDs beginning in 1979 to distinguish such drives as IBM transitioned away from their variable record size format used on IBM's mainframe hard disk drives beginning in 1964 with its System/360.

A master boot record (MBR) is a special type of boot sector at the very beginning of partitioned computer mass storage devices like fixed disks or removable drives intended for use with IBM PC-compatible systems and beyond. The concept of MBRs was publicly introduced in 1983 with PC DOS 2.0.

Ranish Partition Manager is a freeware hard disk partition editor, disk cloning utility, and boot manager, that gives a high level of control for creating multi-boot systems. It is available on the freeware live CD SystemRescueCD and the Ultimate Boot CD. It runs under MS-DOS, PC DOS, DR-DOS, or FreeDOS.

The FAT file system is a file system used on MS-DOS and Windows 9x family of operating systems. It continues to be used on mobile devices and embedded systems, and thus is a well suited file system for data exchange between computers and devices of almost any type and age from 1981 through the present.

References

  1. 1 2 "Information Technology - AT Attachment with Packet Interface - 5 (ATA/ATAPI-5)" (PDF). www.t13.org . 29 February 2000. Archived from the original (PDF) on 6 August 2020. Retrieved 15 December 2020.
  2. "KB224526: Windows NT 4.0 supports maximum of 7.8-GB system partition". Support.microsoft.com. 2007-02-23. Retrieved 2013-07-30.
  3. Steunebrink, Jan. "The BIOS IDE Harddisk Limitations". Archived from the original on 6 October 2013. Retrieved 6 October 2013.
  4. "Information Technology - AT Attachment with Packet Interface - 6 (ATA/ATAPI-6)" (PDF). www.t13.org . 26 February 2002. Archived from the original (PDF) on 6 August 2020. Retrieved 15 December 2020.
  5. "Hard Disk Drive Basics". active-undelete.com. Retrieved 2015-02-10. Track numbers start at 0, and track 0 is the outermost track of the disk. The highest numbered track is next to the spindle.
  6. "Large Disk HOWTO, Section 3. Disk Access". tldp.org. 2004-11-08. Retrieved 2015-02-10.
  7. "The CHS to LBA Conversion Formulas". pcrepairclass.tripod.com. Retrieved 2014-08-26.