Active Block IO Scheduling Subsystem (ABISS)

The Active Block I/O Scheduling System(ABISS)Benno van den BrinkPhilips Research, Eindhoven, The NetherlandsWerner AlmesbergerBuenos Aires, Argentina1

ABISS Extension to Storage subsystem Allow applications to prioritize their I/O Provides a guaranteed hard disk I/O– Make sure the data is there when the application needs it– Provide system-wide control– Make better use of available performance Outline––––Introduction and OverviewImplementationMeasurementsFuture work and Conclusions2

Introduction HDDs in CE equipment Real-time streams: hick-ups are not acceptable– Multiple streams 'PC world' solution: Best Effort performance overkill– Large buffers in application (cost, latency)– Performance (bandwidth, CPU) much higher thanaverage need – over-dimension your system– Cost, power consumption, . Just-in-time: make system guarantee bitrate for RT streams Handle BE traffic in remaining time (make sure there is!)3

Overall architectureABISS daemonapplicationUser spaceKernelABISSVFSPage/buffer cacheelevatorBlock I/ODevice driverdisk4

implementationApplicationUser-spacedaemonPOSIX API (VFS)Configuration interface (ioctl)FilesystemScheduler APIAllocatordriverScheduler coresScheduler libraryPage cache / Page IORequest queue(s)ElevatorBlock device layerBlock device driver5

schedulerApplicationApplication movesplayout pointApplication reads dataSchedulerScheduler caches data locationget blockLocation mapFile systemdriver andVFSPlayout bufferSchedulerprefetches dataScheduler mayupgrade requestsElevatorBlock IO6

Reading block positionstore on-disk locationof RT filesABISS redirects the filesystem's get block functionFile block Disk block Length?File system driver'sget blockLocation map (per file)If file is mapped, uselocation mapIf file is not mapped, use original get block7

Playout bufferApplication playout pointMoves freelyAdvances at the requested rate (or less)Kernel playout pointPage is no longer usedPage is accessible and up to datePage is being loadedPending read request8

Rate controlPlayout points differby more than batch sizeCredit limitDoneCreditNoTimer expiresAdd creditat rate rLoad more ?Reduce credit by onepage and move bufferYescredit 1 page ?1 pageYesNoSet timerSet timer when creditreaches 1 pageReduce credit9

Buffer size Application– Read size– 'jitter' Kernel Elevator disk Read batchingApplication-dependent bufferingRead size or work areaApplication jitterKernel latencyRead batchingIO latencyOperating system and hardwaredependent buffering10

User-space daemon Keeps track of systemwide use Decides whetherbandwidth can be given e.g. ckAdmission controlABISS frameworkSchedulerSet-up data structsgenerate response11

elevatorElevatorAreas (2, read and write)FootprintPriority queues (8)CursorRB treeOverlapsby start sectorSortSort queueBackFIFO queueCurrentLIFO queue321Front12

Scope of elevator and schedulerABISS daemonABISStestABISStestfooanticipatorytest13

API: request ABISS service on filestatic struct abiss attach msg msg;static struct abiss sched test prm prm;fd open("name", O RDONLY);msg.header.type abiss attach;prm.ra bytes app buffer;prm.fill Bps byterate;msg.sched prm &prm;.if (ioctl(fd, ABISS IOCTL, &msg) 0)/* handle error */;FILE *abiss fopen(const char *path, const char*mode, const int byterate, const int app buffer)14

API: update playout pointstatic struct abiss position msg msg;got read(fd, buffer, BUFFER SIZE);msg.header.type abiss position;msg.pos 0;msg.whence SEEK CUR;ioctl(fd, ABISS IOCTL, &msg);abiss fread(void *ptr, size t size, size t nmemb,FILE *fp)15

Measurement H/W setupUSBIEEE 1394CF SlotFastEthernetSingle VoltagePower SupplyCardBus(PCMCIA)SDRAMIDE (2x)Mini PCIPCIGraphicsControllerLegacy I/O(floppy,printer,Game etc)Transmeta Crusoe(800Mhz)DDRAM16

Measurements, description Four RT streams;– 1 MB/s– 64 kB read size– 105 MB files– Playout buffer 564 kB– 20 pages batch size Measure time betweenread request and dataretrieval Loop with BE file copy– 175 MB file– Read size 128 kB Different elevators:– ABISS RT– ABISS BE– Anticipatory– Deadline– CFQ– Noop17

Measurements, graphs18

BE pRT, 10 pg batchRT, 20 pg batchRT, 40 pg batchRT, 80 pg batchRT, 160 pg batchBEBE reader performance [Mbytes/s]One RT reader Four RT .91.87.91.87.92.019

Future work Ext3 filesystem Add RT writing– Investigate buffering requirements– Allocator Different schedulers, e.g. Power for portable players Investigate Asynchronous I/O with elevator priorities20

Conclusions ABISS framework– Allows for different, run-time switchable services– 'test' scheduler implemented– User-space daemon Evaluated performance 'test' scheduler– Guarantee bandwidth without need for large app. buffers– Favorable comparison to existing elevators http://abiss.sourceforge.net/21

Questions?22

ABISSApplicationUser spaceAPI/VFSScheduler &AllocatorElevatorFile System DriverKernelBlock Device LayerDevice DriverHardware23

schedulerTime-driven requestsFile on-drivenrequestsElevatorPage Cache & Block Device LayerScheduler assigns priority24

system overview (detailed)ApplicationMiddlewarePOSIX API (VFS)Configuration interface (ioctl)Allocator APIAllocator coresAllocator libraryScheduler APIFilesystemdriverMM,etc.Scheduler coresNewChangedScheduler libraryPage cache / Page IORequest queue(s)ElevatorBlock device layerBlock device driver25

opening a fileApplicationOpen file, then request ASFS(library uses ASFS IOCTL)MiddlewarePOSIX API (VFS)Configuration interface (ioctl)Scheduler initialized playoutbuffer and asks file systemdriver for file locationScheduler APIFilesystemdriverScheduler coresPlayout bufferScheduler libraryLocation mapPage cache / Page IOBlock device layerBlock device driver26

reading a fileApplicationread() system callReading a file (read)MiddlewarePOSIX API (VFS)File - disk block translationPlayout bufferLocation mapPage(s) in buffer cacheScheduler APINot in cacheScheduler coresScheduler libraryElevator asks schedulerfor priorityRequest queue(s)FilesystemdriverPage cache / Page IOElevatorBlock device layerBlock device driver27

preloading pagesApplicationMove playout point (throughmiddleware and ioctl)MiddlewareScheduler moves playout window,according to rate (timer)POSIX API (VFS)Configuration interface (ioctl)Playout bufferLocation mapScheduler APIScheduler requests new pagesentering playout bufferScheduler coresScheduler libraryElevator asks schedulerfor priorityRequest queue(s)FilesystemdriverPage cache / Page IOElevatorBlock device layerBlock device driver28

playout bufferPlayout buffer/windowBuffer for movement/delay/batchingRead-ahead pagesPlayout pointWork areaPage is loaded and locked in memoryPage is being loadedPage will be loaded laterPage not used anymore29

elevatorPriority 0 (highest, RT only)Priority assignedby schedulerPriority 1Priority 7 (lowest, default)File SystemDriverBest EffortRealTimeDeviceDriverElevator may reorder requestsinside each priority30

Credit & moving playout pointPlayout pointEnough credit ?NoYesApplication movesplayout pointPlayout bufferDrop first page, shift windowMove immediatelyDelayed movement Request new page orupgrade existing requestPage cachePage arrives (in page cache)31

Playout buffer Move playout point (through middleware and ioctl) Scheduler moves playout window, according to rate (timer) Scheduler requests new pages entering playout buffer Elevator asks scheduler for priority system File Scheduler API driver Scheduler cores Scheduler library Page cache / Page IO POSIX API (VFS) Middleware Block device layer .