aboutsummaryrefslogtreecommitdiffstats
BranchCommit messageAuthorAge
archive/unc-master-3.0P-FP: fix BUG_ON releated to priority inheritanceBjoern Brandenburg13 years
archived-2013.1uncachedev: mmap memory that is not cached by CPUsGlenn Elliott12 years
archived-private-masterMerge branch 'wip-2.6.34' into old-private-masterAndrea Bastoni16 years
archived-semi-partMerge branch 'wip-semi-part' of ssh://cvs/cvs/proj/litmus/repo/litmus2010 int...Andrea Bastoni15 years
demoFurther refinementsJonathan Herman14 years
ecrts-pgm-finalMerge branch 'wip-ecrts14-pgm' of ssh://rtsrv.cs.unc.edu/home/litmus/litmus-r...Glenn Elliott12 years
ecrts14-pgm-finalMerge branch 'wip-ecrts14-pgm' of ssh://rtsrv.cs.unc.edu/home/litmus/litmus-r...Glenn Elliott12 years
gpusync-rtss12Final GPUSync implementation.Glenn Elliott13 years
gpusync/stagingRename IKGLP R2DGLP.Glenn Elliott12 years
linux-tipMerge branch 'slab/urgent' of git://git.kernel.org/pub/scm/linux/kernel/git/p...Linus Torvalds15 years
litmus2008-patch-seriesadd i386 feather-trace implementationBjoern B. Brandenburg16 years
masterPSN-EDF: use inferred_sporadic_job_release_atBjoern Brandenburg9 years
pgmmake it compileGlenn Elliott13 years
prop/litmus-signalsInfrastructure for Litmus signals.Glenn Elliott13 years
prop/robust-tie-breakFixed bug in edf_higher_prio().Glenn Elliott13 years
stagingFix tracepoint compilation errorFelipe Cerqueira13 years
test9/23/2016Namhoon Kim9 years
tracing-develTest kernel tracing events capabilitiesAndrea Bastoni16 years
v2.6.34-with-arm-patchessmsc911x: Add spinlocks around registers accessCatalin Marinas16 years
v2015.1Add ARM syscall def for get_current_budgetBjoern Brandenburg10 years
wip-2011.2-bbbLitmus core: simplify np-section protocolBjoern B. Brandenburg14 years
wip-2011.2-bbb-traceRefactor sched_trace_log_message() -> debug_trace_log_message()Andrea Bastoni14 years
wip-2012.3-gpuSOBLIV draining support for C-EDF.Glenn Elliott13 years
wip-2012.3-gpu-preportpick up last C-RM fileGlenn Elliott12 years
wip-2012.3-gpu-rtss13Fix critical bug in GPU tracker.Glenn Elliott12 years
wip-2012.3-gpu-sobliv-budget-w-ksharkProper sobliv draining and many bug fixes.Glenn Elliott13 years
wip-aedzl-finalMake it easier to compile AEDZL interfaces in liblitmus.Glenn Elliott15 years
wip-aedzl-revisedAdd sched_trace data for Apative EDZLGlenn Elliott15 years
wip-arbit-deadlineFix compilation bug.Glenn Elliott13 years
wip-aux-tasksDescription of refined aux task inheritance.Glenn Elliott13 years
wip-bbbGSN-EDF & Core: improve debug TRACE'ing for NP sectionsBjoern B. Brandenburg14 years
wip-bbb-prio-donuse correct timestampBjoern B. Brandenburg14 years
wip-better-breakImplement hash-based EDF tie-breaking.Glenn Elliott13 years
wip-binary-heapMake C-EDF work with simplified binheap_deleteGlenn Elliott14 years
wip-budgetAdded support for choices in budget policy enforcement.Glenn Elliott16 years
wip-colorSummarize schedulability with final recordJonathan Herman14 years
wip-color-jlhsched_color: Fixed two bugs causing crashing on experiment restart and a rare...Jonathan Herman14 years
wip-d10-hz1000Enable HZ=1000 on District 10Bjoern B. Brandenburg15 years
wip-default-clusteringFeature: Make default C-EDF clustering compile-time configurable.Glenn Elliott15 years
wip-dissipation-jericksoUpdate from 2.6.36 to 2.6.36.4Jeremy Erickson12 years
wip-dissipation2-jericksoUpdate 2.6.36 to 2.6.36.4Jeremy Erickson12 years
wip-ecrts14-pgmMerge branch 'wip-ecrts14-pgm' of ssh://rtsrv.cs.unc.edu/home/litmus/litmus-r...Glenn Elliott12 years
wip-edf-hsblast tested versionJonathan Herman14 years
wip-edf-osLookup table EDF-osJeremy Erickson13 years
wip-edf-tie-breakMerge branch 'wip-edf-tie-break' of ssh://rtsrv.cs.unc.edu/home/litmus/litmus...Glenn Elliott13 years
wip-edzl-critiqueUse hr_timer's active checks instead of having own flag.Glenn Elliott15 years
wip-edzl-finalImplementation of the EDZL scheduler.Glenn Elliott15 years
wip-edzl-revisedClean up comments.Glenn Elliott15 years
wip-eventsAdded support for tracing arbitrary actions.Jonathan Herman15 years
wip-extra-debugDBG: add additional tracingBjoern B. Brandenburg15 years
wip-fix-switch-jericksoAttempt to fix race condition with plugin switchingJeremy Erickson15 years
wip-fix3sched: show length of runqueue clock deactivation in /proc/sched_debugBjoern B. Brandenburg15 years
wip-fmlp-dequeueImprove FMLP queue management.Glenn Elliott15 years
wip-ft-irq-flagFeather-Trace: keep track of interrupt-related interference.Bjoern B. Brandenburg14 years
wip-gpu-cleanupEnable sched_trace log injection from userspaceGlenn Elliott13 years
wip-gpu-interruptsRemove option for threading of all softirqs.Glenn Elliott14 years
wip-gpu-rtas12Generalized GPU cost predictors + EWMA. (untested)Glenn Elliott13 years
wip-gpu-rtss12Final GPUSync implementation.Glenn Elliott14 years
wip-gpu-rtss12-srpexperimental changes to support GPUs under SRPGlenn Elliott14 years
wip-gpusync-mergeCleanup priority tracking for budget enforcement.Glenn Elliott12 years
wip-ikglpMove RSM and IKGLP imp. to own .c filesGlenn Elliott14 years
wip-k-fmlpMerge branch 'mpi-master' into wip-k-fmlpGlenn Elliott14 years
wip-kernel-coloringAdded recolor syscallNamhoon Kim8 years
wip-kernthreadsKludge work-queue processing into klitirqd.Glenn Elliott15 years
wip-klmirqd-to-auxAllow klmirqd threads to be given names.Glenn Elliott13 years
wip-ksharkMerge branch 'mpi-staging' into wip-ksharkJonathan Herman13 years
wip-litmus-3.2Merge commit 'v3.2' into litmus-stagingAndrea Bastoni13 years
wip-litmus2011.2Cleanup: Coding conformance for affinity stuff.Glenn Elliott15 years
wip-litmus3.0-2011.2Feather-Trace: keep track of interrupt-related interference.Bjoern B. Brandenburg14 years
wip-master-2.6.33-rtAvoid deadlock when switching task policy to BACKGROUND (ugly)Andrea Bastoni16 years
wip-mcRemoved ARM-specific hacks which disabled less common mixed-criticality featu...Jonathan Herman13 years
wip-mc-bipasaMC-EDF addedbipasa chattopadhyay14 years
wip-mc-jericksoSplit C/D queuesJeremy Erickson15 years
wip-mc2-cache-slackManually patched mc^2 related codeMing Yang10 years
wip-mcrit-maccosmeticMac Mollison15 years
wip-merge-3.0Prevent Linux to send IPI and queue tasks on remote CPUs.Andrea Bastoni14 years
wip-merge-v3.0Prevent Linux to send IPI and queue tasks on remote CPUs.Andrea Bastoni14 years
wip-migration-affinityNULL affinity dereference in C-EDF.Glenn Elliott15 years
wip-mmap-uncacheshare branch with othersGlenn Elliott13 years
wip-modechangeRTSS 2017 submissionNamhoon Kim9 years
wip-nested-lockingAppears to be working.Bryan Ward13 years
wip-omlp-gedfFirst implementation of G-OMLP.Glenn Elliott15 years
wip-paiSome cleanup of PAIGlenn Elliott14 years
wip-percore-lib9/21/2016Namhoon Kim9 years
wip-performanceCONFIG_DONT_PREEMPT_ON_TIE: Don't preeempt a scheduled task on priority tie.Glenn Elliott15 years
wip-pgmAdd PGM support to C-FLGlenn Elliott12 years
wip-pgm-splitFirst draft of C-FL-splitNamhoon Kim12 years
wip-pm-ovdAdd preemption-and-migration overhead tracing supportAndrea Bastoni16 years
wip-prio-inhP-EDF updated to use the generic pi framework.Glenn Elliott15 years
wip-prioq-dglBUG FIX: Support DGLs with PRIOQ_MUTEXGlenn Elliott13 years
wip-refactored-gedfGeneralizd architecture for GEDF-style scheduelrs to reduce code redundancy.Glenn Elliott15 years
wip-release-master-fixbugfix: release master CPU must signal task was pickedBjoern B. Brandenburg15 years
wip-robust-tie-breakEDF priority tie-breaks.Glenn Elliott13 years
wip-rt-ksharkMove task time accounting into the complete_job method.Jonathan Herman13 years
wip-rtas12-pgmScheduling of PGM jobs.Glenn Elliott14 years
wip-semi-partFix compile error with newer GCCJeremy Erickson13 years
wip-semi-part-edfos-jericksoUse initial CPU set by clientJeremy Erickson13 years
wip-shared-libTODO: Fix condition checks in replicate_page_move_mapping()Namhoon Kim9 years
wip-shared-lib2RTAS 2017 Submission ver.Namhoon Kim9 years
wip-shared-memInitial commit for shared libraryNamhoon Kim9 years
wip-splitting-jericksoFix release behaviorJeremy Erickson13 years
wip-splitting-omlp-jericksoBjoern's Dissertation Code with Priority DonationJeremy Erickson13 years
wip-stage-binheapAn efficient binary heap implementation.Glenn Elliott14 years
wip-sun-portDynamic memory allocation and clean exit for FeatherTraceChristopher Kenna15 years
wip-timer-tracebugfix: C-EDF, clear scheduled field of the correct CPU upon task_exitAndrea Bastoni15 years
wip-tracepointsAdd kernel-style events for sched_trace_XXX() functionsAndrea Bastoni14 years
 
TagDownloadAuthorAge
2015.1commit 8e51b37822...Bjoern Brandenburg10 years
2013.1commit bcaacec1ca...Glenn Elliott12 years
2012.3commit c158b5fbe4...Jonathan Herman13 years
2012.2commit b53c479a0f...Glenn Elliott13 years
2012.1commit 83b11ea1c6...Bjoern B. Brandenburg14 years
rtas12-mc-beta-expcommit 8e236ee20f...Christopher Kenna14 years
2011.1commit d11808b5c6...Christopher Kenna15 years
v2.6.37-rc4commit e8a7e48bb2...Linus Torvalds15 years
v2.6.37-rc3commit 3561d43fd2...Linus Torvalds15 years
v2.6.37-rc2commit e53beacd23...Linus Torvalds15 years
v2.6.37-rc1commit c8ddb2713c...Linus Torvalds15 years
v2.6.36commit f6f94e2ab1...Linus Torvalds15 years
2010.2commit 5c5456402d...Bjoern B. Brandenburg15 years
v2.6.36-rc8commit cd07202cc8...Linus Torvalds15 years
v2.6.36-rc7commit cb655d0f3d...Linus Torvalds15 years
v2.6.36-rc6commit 899611ee7d...Linus Torvalds15 years
v2.6.36-rc5commit b30a3f6257...Linus Torvalds15 years
v2.6.36-rc4commit 49553c2ef8...Linus Torvalds15 years
v2.6.36-rc3commit 2bfc96a127...Linus Torvalds15 years
v2.6.36-rc2commit 76be97c1fc...Linus Torvalds15 years
v2.6.36-rc1commit da5cabf80e...Linus Torvalds15 years
v2.6.35commit 9fe6206f40...Linus Torvalds15 years
v2.6.35-rc6commit b37fa16e78...Linus Torvalds15 years
v2.6.35-rc5commit 1c5474a65b...Linus Torvalds16 years
v2.6.35-rc4commit 815c4163b6...Linus Torvalds16 years
v2.6.35-rc3commit 7e27d6e778...Linus Torvalds16 years
v2.6.35-rc2commit e44a21b726...Linus Torvalds16 years
v2.6.35-rc1commit 67a3e12b05...Linus Torvalds16 years
2010.1commit 7c1ff4c544...Andrea Bastoni16 years
v2.6.34commit e40152ee1e...Linus Torvalds16 years
v2.6.33.4commit 4640b4e7d9...Greg Kroah-Hartman16 years
v2.6.34-rc7commit b57f95a382...Linus Torvalds16 years
v2.6.34-rc6commit 66f41d4c5c...Linus Torvalds16 years
v2.6.33.3commit 3e7ad8ed97...Greg Kroah-Hartman16 years
v2.6.34-rc5commit 01bf0b6457...Linus Torvalds16 years
v2.6.34-rc4commit 0d0fb0f9c5...Linus Torvalds16 years
v2.6.33.2commit 19f00f070c...Greg Kroah-Hartman16 years
v2.6.34-rc3commit 2eaa9cfdf3...Linus Torvalds16 years
v2.6.34-rc2commit 220bf991b0...Linus Torvalds16 years
v2.6.33.1commit dbdafe5ccf...Greg Kroah-Hartman16 years
v2.6.34-rc1commit 57d54889cd...Linus Torvalds16 years
v2.6.33commit 60b341b778...Linus Torvalds16 years
v2.6.33-rc8commit 724e6d3fe8...Linus Torvalds16 years
v2.6.33-rc7commit 29275254ca...Linus Torvalds16 years
v2.6.33-rc6commit abe94c756c...Linus Torvalds16 years
v2.6.33-rc5commit 92dcffb916...Linus Torvalds16 years
v2.6.33-rc4commit 7284ce6c9f...Linus Torvalds16 years
v2.6.33-rc3commit 74d2e4f8d7...Linus Torvalds16 years
v2.6.33-rc2commit 6b7b284958...Linus Torvalds16 years
v2.6.33-rc1commit 55639353a0...Linus Torvalds16 years
v2.6.32commit 22763c5cf3...Linus Torvalds16 years
v2.6.32-rc8commit 648f4e3e50...Linus Torvalds16 years
v2.6.32-rc7commit 156171c71a...Linus Torvalds16 years
v2.6.32-rc6commit b419148e56...Linus Torvalds16 years
v2.6.32-rc5commit 012abeea66...Linus Torvalds16 years
v2.6.32-rc4commit 161291396e...Linus Torvalds16 years
v2.6.32-rc3commit 374576a8b6...Linus Torvalds16 years
v2.6.32-rc1commit 17d857be64...Linus Torvalds16 years
v2.6.32-rc2commit 17d857be64...Linus Torvalds16 years
v2.6.31commit 74fca6a428...Linus Torvalds16 years
v2.6.31-rc9commit e07cccf404...Linus Torvalds16 years
v2.6.31-rc8commit 326ba5010a...Linus Torvalds16 years
v2.6.31-rc7commit 422bef879e...Linus Torvalds16 years
v2.6.31-rc6commit 64f1607ffb...Linus Torvalds16 years
v2.6.31-rc5commit ed680c4ad4...Linus Torvalds16 years
v2.6.31-rc4commit 4be3bd7849...Linus Torvalds16 years
v2.6.31-rc3commit 6847e154e3...Linus Torvalds17 years
v2.6.31-rc2commit 8e4a718ff3...Linus Torvalds17 years
v2.6.31-rc1commit 28d0325ce6...Linus Torvalds17 years
v2.6.30commit 07a2039b8e...Linus Torvalds17 years
v2.6.30-rc8commit 9fa7eb283c...Linus Torvalds17 years
v2.6.30-rc7commit 59a3759d0f...Linus Torvalds17 years
v2.6.30-rc6commit 1406de8e11...Linus Torvalds17 years
v2.6.30-rc5commit 091bf7624d...Linus Torvalds17 years
v2.6.30-rc4commit 091438dd56...Linus Torvalds17 years
v2.6.30-rc3commit 0910697403...Linus Torvalds17 years
v2.6.30-rc2commit 0882e8dd3a...Linus Torvalds17 years
v2.6.30-rc1commit 577c9c456f...Linus Torvalds17 years
v2.6.29commit 8e0ee43bc2...Linus Torvalds17 years
v2.6.29-rc8commit 041b62374c...Linus Torvalds17 years
v2.6.29-rc7commit fec6c6fec3...Linus Torvalds17 years
v2.6.29-rc6commit 20f4d6c3a2...Linus Torvalds17 years
v2.6.29-rc5commit d2f8d7ee1a...Linus Torvalds17 years
v2.6.29-rc4commit 8e4921515c...Linus Torvalds17 years
v2.6.29-rc3commit 18e352e4a7...Linus Torvalds17 years
v2.6.29-rc2commit 1de9e8e70f...Linus Torvalds17 years
v2.6.29-rc1commit c59765042f...Linus Torvalds17 years
v2.6.28commit 4a6908a3a0...Linus Torvalds17 years
v2.6.28-rc9commit 929096fe9f...Linus Torvalds17 years
v2.6.28-rc8commit 8b1fae4e42...Linus Torvalds17 years
v2.6.28-rc7commit 061e41fdb5...Linus Torvalds17 years
v2.6.28-rc6commit 13d428afc0...Linus Torvalds17 years
v2.6.28-rc5commit 9bf1a2445f...Linus Torvalds17 years
v2.6.28-rc4commit f7160c7573...Linus Torvalds17 years
v2.6.28-rc3commit 45beca08dd...Linus Torvalds17 years
v2.6.28-rc2commit 0173a3265b...Linus Torvalds17 years
v2.6.28-rc1commit 57f8f7b60d...Linus Torvalds17 years
v2.6.27commit 3fa8749e58...Linus Torvalds17 years
v2.6.27-rc9commit 4330ed8ed4...Linus Torvalds17 years
v2.6.27-rc8commit 94aca1dac6...Linus Torvalds17 years
v2.6.27-rc7commit 72d31053f6...Linus Torvalds17 years
v2.6.27-rc6commit adee14b2e1...Linus Torvalds17 years
v2.6.27-rc5commit 24342c34a0...Linus Torvalds17 years
v2.6.27-rc4commit 6a55617ed5...Linus Torvalds17 years
v2.6.27-rc3commit 30a2f3c60a...Linus Torvalds17 years
v2.6.27-rc2commit 0967d61ea0...Linus Torvalds17 years
v2.6.27-rc1commit 6e86841d05...Linus Torvalds17 years
v2.6.26commit bce7f793da...Linus Torvalds18 years
v2.6.26-rc9commit b7279469d6...Linus Torvalds18 years
v2.6.26-rc8commit 543cf4cb3f...Linus Torvalds18 years
v2.6.26-rc7commit d70ac829b7...Linus Torvalds18 years
v2.6.26-rc6commit 5dd34572ad...Linus Torvalds18 years
v2.6.26-rc5commit 53c8ba9540...Linus Torvalds18 years
v2.6.26-rc4commit e490517a03...Linus Torvalds18 years
v2.6.26-rc3commit b8291ad07a...Linus Torvalds18 years
v2.6.26-rc2commit 492c2e476e...Linus Torvalds18 years
v2.6.26-rc1commit 2ddcca36c8...Linus Torvalds18 years
v2.6.25commit 4b119e21d0...Linus Torvalds18 years
v2.6.25-rc9commit 120dd64cac...Linus Torvalds18 years
v2.6.25-rc8commit 0e81a8ae37...Linus Torvalds18 years
v2.6.25-rc7commit 05dda977f2...Linus Torvalds18 years
v2.6.25-rc6commit a978b30af3...Linus Torvalds18 years
v2.6.25-rc5commit cdeeeae056...Linus Torvalds18 years
v2.6.25-rc4commit 29e8c3c304...Linus Torvalds18 years
v2.6.25-rc3commit bfa274e243...Linus Torvalds18 years
v2.6.25-rc2commit 101142c37b...Linus Torvalds18 years
v2.6.25-rc1commit 19af35546d...Linus Torvalds18 years
v2.6.24commit 49914084e7...Linus Torvalds18 years
v2.6.24-rc8commit cbd9c88369...Linus Torvalds18 years
v2.6.24-rc7commit 3ce5445046...Linus Torvalds18 years
v2.6.24-rc6commit ea67db4cdb...Linus Torvalds18 years
v2.6.24-rc5commit 82d29bf6dc...Linus Torvalds18 years
v2.6.24-rc4commit 09b56adc98...Linus Torvalds18 years
v2.6.24-rc3commit d9f8bcbf67...Linus Torvalds18 years
v2.6.24-rc2commit dbeeb816e8...Linus Torvalds18 years
v2.6.24-rc1commit c9927c2bf4...Linus Torvalds18 years
v2.6.23commit bbf25010f1...Linus Torvalds18 years
v2.6.23-rc9commit 3146b39c18...Linus Torvalds18 years
v2.6.23-rc8commit 4942de4a0e...Linus Torvalds18 years
v2.6.23-rc7commit 81cfe79b9c...Linus Torvalds18 years
v2.6.23-rc6commit 0d4cbb5e7f...Linus Torvalds18 years
v2.6.23-rc5commit 40ffbfad6b...Linus Torvalds18 years
v2.6.23-rc4commit b07d68b5ca...Linus Torvalds18 years
v2.6.23-rc3commit 39d3520c92...Linus Torvalds18 years
v2.6.23-rc2commit d4ac2477fa...Linus Torvalds18 years
v2.6.23-rc1commit f695baf2df...Linus Torvalds18 years
v2.6.22commit 7dcca30a32...Linus Torvalds19 years
v2.6.22-rc7commit a38d6181ff...Linus Torvalds19 years
v2.6.22-rc6commit 189548642c...Linus Torvalds19 years
v2.6.22-rc5commit 188e1f81ba...Linus Torvalds19 years
v2.6.22-rc4commit 5ecd3100e6...Linus Torvalds19 years
v2.6.22-rc3commit c420bc9f09...Linus Torvalds19 years
v2.6.22-rc2commit 55b637c6a0...Linus Torvalds19 years
v2.6.22-rc1commit 39403865d2...Linus Torvalds19 years
v2.6.21commit de46c33745...Linus Torvalds19 years
v2.6.21-rc7commit 94a05509a9...Linus Torvalds19 years
v2.6.21-rc6commit a21bd69e15...Linus Torvalds19 years
v2.6.21-rc5commit e0f2e3a06b...Linus Torvalds19 years
v2.6.21-rc4commit db98e0b434...Linus Torvalds19 years
v2.6.21-rc3commit 08e15e81a4...Linus Torvalds19 years
v2.6.21-rc2commit 606135a308...Linus Torvalds19 years
v2.6.21-rc1commit c8f71b01a5...Linus Torvalds19 years
v2.6.20commit 62d0cfcb27...Linus Torvalds19 years
v2.6.20-rc7commit f56df2f4db...Linus Torvalds19 years
v2.6.20-rc6commit 99abfeafb5...Linus Torvalds19 years
v2.6.20-rc5commit a8b3485287...Linus Torvalds19 years
v2.6.20-rc4commit bf81b46482...Linus Torvalds19 years
v2.6.20-rc3commit 669df1b478...Linus Torvalds19 years
v2.6.20-rc2commit 3bf8ba38f3...Linus Torvalds19 years
v2.6.20-rc1commit cc016448b0...Linus Torvalds19 years
v2.6.19commit 0215ffb08c...Linus Torvalds19 years
v2.6.19-rc6commit 44597f65f6...Linus Torvalds19 years
v2.6.19-rc5commit 80c2188127...Linus Torvalds19 years
v2.6.19-rc4commit ae99a78af3...Linus Torvalds19 years
v2.6.19-rc3commit 7059abedd2...Linus Torvalds19 years
v2.6.19-rc2commit b4bd8c6643...Linus Torvalds19 years
v2.6.19-rc1commit d223a60106...Linus Torvalds19 years
v2.6.18commit e478bec0ba...Linus Torvalds19 years
v2.6.18-rc7commit 95064a75eb...Linus Torvalds19 years
v2.6.18-rc6commit c336923b66...Linus Torvalds19 years
v2.6.18-rc5commit 60d4684068...Linus Torvalds19 years
v2.6.18-rc4commit 9f737633e6...Linus Torvalds19 years
v2.6.18-rc3commit b6ff50833a...Linus Torvalds19 years
v2.6.18-rc2commit 82d6897fef...Linus Torvalds19 years
v2.6.18-rc1commit 120bda20c6...Linus Torvalds20 years
v2.6.17commit 427abfa28a...Linus Torvalds20 years
v2.6.17-rc6commit 1def630a6a...Linus Torvalds20 years
v2.6.17-rc5commit a8bd60705a...Linus Torvalds20 years
v2.6.17-rc4commit d8c3291c73...Linus Torvalds20 years
v2.6.17-rc3commit 2be4d50295...Linus Torvalds20 years
v2.6.17-rc2commit 8bbde0e6d5...Linus Torvalds20 years
v2.6.17-rc1commit 6246b6128b...Linus Torvalds20 years
v2.6.16commit 7705a8792b...Linus Torvalds20 years
v2.6.16-rc6commit 535744878e...Linus Torvalds20 years
v2.6.16-rc5commit b9a33cebac...Linus Torvalds20 years
v2.6.16-rc4commit bd71c2b174...Linus Torvalds20 years
v2.6.16-rc3commit e9bb4c9929...Linus Torvalds20 years
v2.6.16-rc2commit 826eeb53a6...Linus Torvalds20 years
v2.6.16-rc1commit 2664b25051...Linus Torvalds20 years
v2.6.15commit 88026842b0...Linus Torvalds20 years
v2.6.15-rc7commit f89f5948fc...Linus Torvalds20 years
v2.6.15-rc6commit df7addbb45...Linus Torvalds20 years
v2.6.15-rc5commit 436b0f76f2...Linus Torvalds20 years
v2.6.15-rc4commit 5666c0947e...Linus Torvalds20 years
v2.6.15-rc3commit 624f54be20...Linus Torvalds20 years
v2.6.15-rc2commit 3bedff1d73...Linus Torvalds20 years
v2.6.15-rc1commit cd52d1ee9a...Linus Torvalds20 years
v2.6.14commit 741b2252a5...Linus Torvalds20 years
v2.6.14-rc5commit 93918e9afc...Linus Torvalds20 years
v2.6.14-rc4commit 907a426179...Linus Torvalds20 years
v2.6.14-rc3commit 1c9426e8a5...Linus Torvalds20 years
v2.6.14-rc2commit 676d55ae30...Linus Torvalds20 years
v2.6.14-rc1commit 2f4ba45a75...Linus Torvalds20 years
v2.6.13commit 02b3e4e2d7...Linus Torvalds20 years
v2.6.13-rc7commit 0572e3da3f...Linus Torvalds20 years
v2.6.13-rc6commit 6fc32179de...Linus Torvalds20 years
v2.6.13-rc5commit 9a351e30d7...Linus Torvalds20 years
v2.6.13-rc4commit 6395352334...Linus Torvalds20 years
v2.6.11tree c39ae07f39...
v2.6.11-treetree c39ae07f39...
v2.6.12commit 9ee1c939d1...
v2.6.12-rc2commit 1da177e4c3...
v2.6.12-rc3commit a2755a80f4...
v2.6.12-rc4commit 88d7bd8cb9...
v2.6.12-rc5commit 2a24ab628a...
v2.6.12-rc6commit 7cef5677ef...
v2.6.13-rc1commit 4c91aedb75...
v2.6.13-rc2commit a18bcb7450...
v2.6.13-rc3commit c32511e271...
n class="hl kwb">int)((char *)&oldroot->btree[be16_to_cpu(oldroot->hdr.count)] - (char *)oldroot); } else { ASSERT(be16_to_cpu(oldroot->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC); leaf = (xfs_dir2_leaf_t *)oldroot; size = (int)((char *)&leaf->ents[be16_to_cpu(leaf->hdr.count)] - (char *)leaf); } memcpy(node, oldroot, size); xfs_da_log_buf(tp, bp, 0, size - 1); xfs_da_buf_done(blk1->bp); blk1->bp = bp; blk1->blkno = blkno; /* * Set up the new root node. */ error = xfs_da_node_create(args, (args->whichfork == XFS_DATA_FORK) ? mp->m_dirleafblk : 0, be16_to_cpu(node->hdr.level) + 1, &bp, args->whichfork); if (error) return(error); node = bp->data; node->btree[0].hashval = cpu_to_be32(blk1->hashval); node->btree[0].before = cpu_to_be32(blk1->blkno); node->btree[1].hashval = cpu_to_be32(blk2->hashval); node->btree[1].before = cpu_to_be32(blk2->blkno); node->hdr.count = cpu_to_be16(2); #ifdef DEBUG if (be16_to_cpu(oldroot->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC) { ASSERT(blk1->blkno >= mp->m_dirleafblk && blk1->blkno < mp->m_dirfreeblk); ASSERT(blk2->blkno >= mp->m_dirleafblk && blk2->blkno < mp->m_dirfreeblk); } #endif /* Header is already logged by xfs_da_node_create */ xfs_da_log_buf(tp, bp, XFS_DA_LOGRANGE(node, node->btree, sizeof(xfs_da_node_entry_t) * 2)); xfs_da_buf_done(bp); return(0); } /* * Split the node, rebalance, then add the new entry. */ STATIC int /* error */ xfs_da_node_split(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk, xfs_da_state_blk_t *newblk, xfs_da_state_blk_t *addblk, int treelevel, int *result) { xfs_da_intnode_t *node; xfs_dablk_t blkno; int newcount, error; int useextra; node = oldblk->bp->data; ASSERT(be16_to_cpu(node->hdr.info.magic) == XFS_DA_NODE_MAGIC); /* * With V2 dirs the extra block is data or freespace. */ useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK; newcount = 1 + useextra; /* * Do we have to split the node? */ if ((be16_to_cpu(node->hdr.count) + newcount) > state->node_ents) { /* * Allocate a new node, add to the doubly linked chain of * nodes, then move some of our excess entries into it. */ error = xfs_da_grow_inode(state->args, &blkno); if (error) return(error); /* GROT: dir is inconsistent */ error = xfs_da_node_create(state->args, blkno, treelevel, &newblk->bp, state->args->whichfork); if (error) return(error); /* GROT: dir is inconsistent */ newblk->blkno = blkno; newblk->magic = XFS_DA_NODE_MAGIC; xfs_da_node_rebalance(state, oldblk, newblk); error = xfs_da_blk_link(state, oldblk, newblk); if (error) return(error); *result = 1; } else { *result = 0; } /* * Insert the new entry(s) into the correct block * (updating last hashval in the process). * * xfs_da_node_add() inserts BEFORE the given index, * and as a result of using node_lookup_int() we always * point to a valid entry (not after one), but a split * operation always results in a new block whose hashvals * FOLLOW the current block. * * If we had double-split op below us, then add the extra block too. */ node = oldblk->bp->data; if (oldblk->index <= be16_to_cpu(node->hdr.count)) { oldblk->index++; xfs_da_node_add(state, oldblk, addblk); if (useextra) { if (state->extraafter) oldblk->index++; xfs_da_node_add(state, oldblk, &state->extrablk); state->extravalid = 0; } } else { newblk->index++; xfs_da_node_add(state, newblk, addblk); if (useextra) { if (state->extraafter) newblk->index++; xfs_da_node_add(state, newblk, &state->extrablk); state->extravalid = 0; } } return(0); } /* * Balance the btree elements between two intermediate nodes, * usually one full and one empty. * * NOTE: if blk2 is empty, then it will get the upper half of blk1. */ STATIC void xfs_da_node_rebalance(xfs_da_state_t *state, xfs_da_state_blk_t *blk1, xfs_da_state_blk_t *blk2) { xfs_da_intnode_t *node1, *node2, *tmpnode; xfs_da_node_entry_t *btree_s, *btree_d; int count, tmp; xfs_trans_t *tp; node1 = blk1->bp->data; node2 = blk2->bp->data; /* * Figure out how many entries need to move, and in which direction. * Swap the nodes around if that makes it simpler. */ if ((be16_to_cpu(node1->hdr.count) > 0) && (be16_to_cpu(node2->hdr.count) > 0) && ((be32_to_cpu(node2->btree[0].hashval) < be32_to_cpu(node1->btree[0].hashval)) || (be32_to_cpu(node2->btree[be16_to_cpu(node2->hdr.count)-1].hashval) < be32_to_cpu(node1->btree[be16_to_cpu(node1->hdr.count)-1].hashval)))) { tmpnode = node1; node1 = node2; node2 = tmpnode; } ASSERT(be16_to_cpu(node1->hdr.info.magic) == XFS_DA_NODE_MAGIC); ASSERT(be16_to_cpu(node2->hdr.info.magic) == XFS_DA_NODE_MAGIC); count = (be16_to_cpu(node1->hdr.count) - be16_to_cpu(node2->hdr.count)) / 2; if (count == 0) return; tp = state->args->trans; /* * Two cases: high-to-low and low-to-high. */ if (count > 0) { /* * Move elements in node2 up to make a hole. */ if ((tmp = be16_to_cpu(node2->hdr.count)) > 0) { tmp *= (uint)sizeof(xfs_da_node_entry_t); btree_s = &node2->btree[0]; btree_d = &node2->btree[count]; memmove(btree_d, btree_s, tmp); } /* * Move the req'd B-tree elements from high in node1 to * low in node2. */ be16_add_cpu(&node2->hdr.count, count); tmp = count * (uint)sizeof(xfs_da_node_entry_t); btree_s = &node1->btree[be16_to_cpu(node1->hdr.count) - count]; btree_d = &node2->btree[0]; memcpy(btree_d, btree_s, tmp); be16_add_cpu(&node1->hdr.count, -count); } else { /* * Move the req'd B-tree elements from low in node2 to * high in node1. */ count = -count; tmp = count * (uint)sizeof(xfs_da_node_entry_t); btree_s = &node2->btree[0]; btree_d = &node1->btree[be16_to_cpu(node1->hdr.count)]; memcpy(btree_d, btree_s, tmp); be16_add_cpu(&node1->hdr.count, count); xfs_da_log_buf(tp, blk1->bp, XFS_DA_LOGRANGE(node1, btree_d, tmp)); /* * Move elements in node2 down to fill the hole. */ tmp = be16_to_cpu(node2->hdr.count) - count; tmp *= (uint)sizeof(xfs_da_node_entry_t); btree_s = &node2->btree[count]; btree_d = &node2->btree[0]; memmove(btree_d, btree_s, tmp); be16_add_cpu(&node2->hdr.count, -count); } /* * Log header of node 1 and all current bits of node 2. */ xfs_da_log_buf(tp, blk1->bp, XFS_DA_LOGRANGE(node1, &node1->hdr, sizeof(node1->hdr))); xfs_da_log_buf(tp, blk2->bp, XFS_DA_LOGRANGE(node2, &node2->hdr, sizeof(node2->hdr) + sizeof(node2->btree[0]) * be16_to_cpu(node2->hdr.count))); /* * Record the last hashval from each block for upward propagation. * (note: don't use the swapped node pointers) */ node1 = blk1->bp->data; node2 = blk2->bp->data; blk1->hashval = be32_to_cpu(node1->btree[be16_to_cpu(node1->hdr.count)-1].hashval); blk2->hashval = be32_to_cpu(node2->btree[be16_to_cpu(node2->hdr.count)-1].hashval); /* * Adjust the expected index for insertion. */ if (blk1->index >= be16_to_cpu(node1->hdr.count)) { blk2->index = blk1->index - be16_to_cpu(node1->hdr.count); blk1->index = be16_to_cpu(node1->hdr.count) + 1; /* make it invalid */ } } /* * Add a new entry to an intermediate node. */ STATIC void xfs_da_node_add(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk, xfs_da_state_blk_t *newblk) { xfs_da_intnode_t *node; xfs_da_node_entry_t *btree; int tmp; xfs_mount_t *mp; node = oldblk->bp->data; mp = state->mp; ASSERT(be16_to_cpu(node->hdr.info.magic) == XFS_DA_NODE_MAGIC); ASSERT((oldblk->index >= 0) && (oldblk->index <= be16_to_cpu(node->hdr.count))); ASSERT(newblk->blkno != 0); if (state->args->whichfork == XFS_DATA_FORK) ASSERT(newblk->blkno >= mp->m_dirleafblk && newblk->blkno < mp->m_dirfreeblk); /* * We may need to make some room before we insert the new node. */ tmp = 0; btree = &node->btree[ oldblk->index ]; if (oldblk->index < be16_to_cpu(node->hdr.count)) { tmp = (be16_to_cpu(node->hdr.count) - oldblk->index) * (uint)sizeof(*btree); memmove(btree + 1, btree, tmp); } btree->hashval = cpu_to_be32(newblk->hashval); btree->before = cpu_to_be32(newblk->blkno); xfs_da_log_buf(state->args->trans, oldblk->bp, XFS_DA_LOGRANGE(node, btree, tmp + sizeof(*btree))); be16_add_cpu(&node->hdr.count, 1); xfs_da_log_buf(state->args->trans, oldblk->bp, XFS_DA_LOGRANGE(node, &node->hdr, sizeof(node->hdr))); /* * Copy the last hash value from the oldblk to propagate upwards. */ oldblk->hashval = be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1 ].hashval); } /*======================================================================== * Routines used for shrinking the Btree. *========================================================================*/ /* * Deallocate an empty leaf node, remove it from its parent, * possibly deallocating that block, etc... */ int xfs_da_join(xfs_da_state_t *state) { xfs_da_state_blk_t *drop_blk, *save_blk; int action, error; action = 0; drop_blk = &state->path.blk[ state->path.active-1 ]; save_blk = &state->altpath.blk[ state->path.active-1 ]; ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC); ASSERT(drop_blk->magic == XFS_ATTR_LEAF_MAGIC || drop_blk->magic == XFS_DIR2_LEAFN_MAGIC); /* * Walk back up the tree joining/deallocating as necessary. * When we stop dropping blocks, break out. */ for ( ; state->path.active >= 2; drop_blk--, save_blk--, state->path.active--) { /* * See if we can combine the block with a neighbor. * (action == 0) => no options, just leave * (action == 1) => coalesce, then unlink * (action == 2) => block empty, unlink it */ switch (drop_blk->magic) { case XFS_ATTR_LEAF_MAGIC: error = xfs_attr_leaf_toosmall(state, &action); if (error) return(error); if (action == 0) return(0); xfs_attr_leaf_unbalance(state, drop_blk, save_blk); break; case XFS_DIR2_LEAFN_MAGIC: error = xfs_dir2_leafn_toosmall(state, &action); if (error) return error; if (action == 0) return 0; xfs_dir2_leafn_unbalance(state, drop_blk, save_blk); break; case XFS_DA_NODE_MAGIC: /* * Remove the offending node, fixup hashvals, * check for a toosmall neighbor. */ xfs_da_node_remove(state, drop_blk); xfs_da_fixhashpath(state, &state->path); error = xfs_da_node_toosmall(state, &action); if (error) return(error); if (action == 0) return 0; xfs_da_node_unbalance(state, drop_blk, save_blk); break; } xfs_da_fixhashpath(state, &state->altpath); error = xfs_da_blk_unlink(state, drop_blk, save_blk); xfs_da_state_kill_altpath(state); if (error) return(error); error = xfs_da_shrink_inode(state->args, drop_blk->blkno, drop_blk->bp); drop_blk->bp = NULL; if (error) return(error); } /* * We joined all the way to the top. If it turns out that * we only have one entry in the root, make the child block * the new root. */ xfs_da_node_remove(state, drop_blk); xfs_da_fixhashpath(state, &state->path); error = xfs_da_root_join(state, &state->path.blk[0]); return(error); } /* * We have only one entry in the root. Copy the only remaining child of * the old root to block 0 as the new root node. */ STATIC int xfs_da_root_join(xfs_da_state_t *state, xfs_da_state_blk_t *root_blk) { xfs_da_intnode_t *oldroot; /* REFERENCED */ xfs_da_blkinfo_t *blkinfo; xfs_da_args_t *args; xfs_dablk_t child; xfs_dabuf_t *bp; int error; args = state->args; ASSERT(args != NULL); ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC); oldroot = root_blk->bp->data; ASSERT(be16_to_cpu(oldroot->hdr.info.magic) == XFS_DA_NODE_MAGIC); ASSERT(!oldroot->hdr.info.forw); ASSERT(!oldroot->hdr.info.back); /* * If the root has more than one child, then don't do anything. */ if (be16_to_cpu(oldroot->hdr.count) > 1) return(0); /* * Read in the (only) child block, then copy those bytes into * the root block's buffer and free the original child block. */ child = be32_to_cpu(oldroot->btree[0].before); ASSERT(child != 0); error = xfs_da_read_buf(args->trans, args->dp, child, -1, &bp, args->whichfork); if (error) return(error); ASSERT(bp != NULL); blkinfo = bp->data; if (be16_to_cpu(oldroot->hdr.level) == 1) { ASSERT(be16_to_cpu(blkinfo->magic) == XFS_DIR2_LEAFN_MAGIC || be16_to_cpu(blkinfo->magic) == XFS_ATTR_LEAF_MAGIC); } else { ASSERT(be16_to_cpu(blkinfo->magic) == XFS_DA_NODE_MAGIC); } ASSERT(!blkinfo->forw); ASSERT(!blkinfo->back); memcpy(root_blk->bp->data, bp->data, state->blocksize); xfs_da_log_buf(args->trans, root_blk->bp, 0, state->blocksize - 1); error = xfs_da_shrink_inode(args, child, bp); return(error); } /* * Check a node block and its neighbors to see if the block should be * collapsed into one or the other neighbor. Always keep the block * with the smaller block number. * If the current block is over 50% full, don't try to join it, return 0. * If the block is empty, fill in the state structure and return 2. * If it can be collapsed, fill in the state structure and return 1. * If nothing can be done, return 0. */ STATIC int xfs_da_node_toosmall(xfs_da_state_t *state, int *action) { xfs_da_intnode_t *node; xfs_da_state_blk_t *blk; xfs_da_blkinfo_t *info; int count, forward, error, retval, i; xfs_dablk_t blkno; xfs_dabuf_t *bp; /* * Check for the degenerate case of the block being over 50% full. * If so, it's not worth even looking to see if we might be able * to coalesce with a sibling. */ blk = &state->path.blk[ state->path.active-1 ]; info = blk->bp->data; ASSERT(be16_to_cpu(info->magic) == XFS_DA_NODE_MAGIC); node = (xfs_da_intnode_t *)info; count = be16_to_cpu(node->hdr.count); if (count > (state->node_ents >> 1)) { *action = 0; /* blk over 50%, don't try to join */ return(0); /* blk over 50%, don't try to join */ } /* * Check for the degenerate case of the block being empty. * If the block is empty, we'll simply delete it, no need to * coalesce it with a sibling block. We choose (arbitrarily) * to merge with the forward block unless it is NULL. */ if (count == 0) { /* * Make altpath point to the block we want to keep and * path point to the block we want to drop (this one). */ forward = (info->forw != 0); memcpy(&state->altpath, &state->path, sizeof(state->path)); error = xfs_da_path_shift(state, &state->altpath, forward, 0, &retval); if (error) return(error); if (retval) { *action = 0; } else { *action = 2; } return(0); } /* * Examine each sibling block to see if we can coalesce with * at least 25% free space to spare. We need to figure out * whether to merge with the forward or the backward block. * We prefer coalescing with the lower numbered sibling so as * to shrink a directory over time. */ /* start with smaller blk num */ forward = (be32_to_cpu(info->forw) < be32_to_cpu(info->back)); for (i = 0; i < 2; forward = !forward, i++) { if (forward) blkno = be32_to_cpu(info->forw); else blkno = be32_to_cpu(info->back); if (blkno == 0) continue; error = xfs_da_read_buf(state->args->trans, state->args->dp, blkno, -1, &bp, state->args->whichfork); if (error) return(error); ASSERT(bp != NULL); node = (xfs_da_intnode_t *)info; count = state->node_ents; count -= state->node_ents >> 2; count -= be16_to_cpu(node->hdr.count); node = bp->data; ASSERT(be16_to_cpu(node->hdr.info.magic) == XFS_DA_NODE_MAGIC); count -= be16_to_cpu(node->hdr.count); xfs_da_brelse(state->args->trans, bp); if (count >= 0) break; /* fits with at least 25% to spare */ } if (i >= 2) { *action = 0; return(0); } /* * Make altpath point to the block we want to keep (the lower * numbered block) and path point to the block we want to drop. */ memcpy(&state->altpath, &state->path, sizeof(state->path)); if (blkno < blk->blkno) { error = xfs_da_path_shift(state, &state->altpath, forward, 0, &retval); if (error) { return(error); } if (retval) { *action = 0; return(0); } } else { error = xfs_da_path_shift(state, &state->path, forward, 0, &retval); if (error) { return(error); } if (retval) { *action = 0; return(0); } } *action = 1; return(0); } /* * Walk back up the tree adjusting hash values as necessary, * when we stop making changes, return. */ void xfs_da_fixhashpath(xfs_da_state_t *state, xfs_da_state_path_t *path) { xfs_da_state_blk_t *blk; xfs_da_intnode_t *node; xfs_da_node_entry_t *btree; xfs_dahash_t lasthash=0; int level, count; level = path->active-1; blk = &path->blk[ level ]; switch (blk->magic) { case XFS_ATTR_LEAF_MAGIC: lasthash = xfs_attr_leaf_lasthash(blk->bp, &count); if (count == 0) return; break; case XFS_DIR2_LEAFN_MAGIC: lasthash = xfs_dir2_leafn_lasthash(blk->bp, &count); if (count == 0) return; break; case XFS_DA_NODE_MAGIC: lasthash = xfs_da_node_lasthash(blk->bp, &count); if (count == 0) return; break; } for (blk--, level--; level >= 0; blk--, level--) { node = blk->bp->data; ASSERT(be16_to_cpu(node->hdr.info.magic) == XFS_DA_NODE_MAGIC); btree = &node->btree[ blk->index ]; if (be32_to_cpu(btree->hashval) == lasthash) break; blk->hashval = lasthash; btree->hashval = cpu_to_be32(lasthash); xfs_da_log_buf(state->args->trans, blk->bp, XFS_DA_LOGRANGE(node, btree, sizeof(*btree))); lasthash = be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1].hashval); } } /* * Remove an entry from an intermediate node. */ STATIC void xfs_da_node_remove(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk) { xfs_da_intnode_t *node; xfs_da_node_entry_t *btree; int tmp; node = drop_blk->bp->data; ASSERT(drop_blk->index < be16_to_cpu(node->hdr.count)); ASSERT(drop_blk->index >= 0); /* * Copy over the offending entry, or just zero it out. */ btree = &node->btree[drop_blk->index]; if (drop_blk->index < (be16_to_cpu(node->hdr.count)-1)) { tmp = be16_to_cpu(node->hdr.count) - drop_blk->index - 1; tmp *= (uint)sizeof(xfs_da_node_entry_t); memmove(btree, btree + 1, tmp); xfs_da_log_buf(state->args->trans, drop_blk->bp, XFS_DA_LOGRANGE(node, btree, tmp)); btree = &node->btree[be16_to_cpu(node->hdr.count)-1]; } memset((char *)btree, 0, sizeof(xfs_da_node_entry_t)); xfs_da_log_buf(state->args->trans, drop_blk->bp, XFS_DA_LOGRANGE(node, btree, sizeof(*btree))); be16_add_cpu(&node->hdr.count, -1); xfs_da_log_buf(state->args->trans, drop_blk->bp, XFS_DA_LOGRANGE(node, &node->hdr, sizeof(node->hdr))); /* * Copy the last hash value from the block to propagate upwards. */ btree--; drop_blk->hashval = be32_to_cpu(btree->hashval); } /* * Unbalance the btree elements between two intermediate nodes, * move all Btree elements from one node into another. */ STATIC void xfs_da_node_unbalance(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk, xfs_da_state_blk_t *save_blk) { xfs_da_intnode_t *drop_node, *save_node; xfs_da_node_entry_t *btree; int tmp; xfs_trans_t *tp; drop_node = drop_blk->bp->data; save_node = save_blk->bp->data; ASSERT(be16_to_cpu(drop_node->hdr.info.magic) == XFS_DA_NODE_MAGIC); ASSERT(be16_to_cpu(save_node->hdr.info.magic) == XFS_DA_NODE_MAGIC); tp = state->args->trans; /* * If the dying block has lower hashvals, then move all the * elements in the remaining block up to make a hole. */ if ((be32_to_cpu(drop_node->btree[0].hashval) < be32_to_cpu(save_node->btree[ 0 ].hashval)) || (be32_to_cpu(drop_node->btree[be16_to_cpu(drop_node->hdr.count)-1].hashval) < be32_to_cpu(save_node->btree[be16_to_cpu(save_node->hdr.count)-1].hashval))) { btree = &save_node->btree[be16_to_cpu(drop_node->hdr.count)]; tmp = be16_to_cpu(save_node->hdr.count) * (uint)sizeof(xfs_da_node_entry_t); memmove(btree, &save_node->btree[0], tmp); btree = &save_node->btree[0]; xfs_da_log_buf(tp, save_blk->bp, XFS_DA_LOGRANGE(save_node, btree, (be16_to_cpu(save_node->hdr.count) + be16_to_cpu(drop_node->hdr.count)) * sizeof(xfs_da_node_entry_t))); } else { btree = &save_node->btree[be16_to_cpu(save_node->hdr.count)]; xfs_da_log_buf(tp, save_blk->bp, XFS_DA_LOGRANGE(save_node, btree, be16_to_cpu(drop_node->hdr.count) * sizeof(xfs_da_node_entry_t))); } /* * Move all the B-tree elements from drop_blk to save_blk. */ tmp = be16_to_cpu(drop_node->hdr.count) * (uint)sizeof(xfs_da_node_entry_t); memcpy(btree, &drop_node->btree[0], tmp); be16_add_cpu(&save_node->hdr.count, be16_to_cpu(drop_node->hdr.count)); xfs_da_log_buf(tp, save_blk->bp, XFS_DA_LOGRANGE(save_node, &save_node->hdr, sizeof(save_node->hdr))); /* * Save the last hashval in the remaining block for upward propagation. */ save_blk->hashval = be32_to_cpu(save_node->btree[be16_to_cpu(save_node->hdr.count)-1].hashval); } /*======================================================================== * Routines used for finding things in the Btree. *========================================================================*/ /* * Walk down the Btree looking for a particular filename, filling * in the state structure as we go. * * We will set the state structure to point to each of the elements * in each of the nodes where either the hashval is or should be. * * We support duplicate hashval's so for each entry in the current * node that could contain the desired hashval, descend. This is a * pruned depth-first tree search. */ int /* error */ xfs_da_node_lookup_int(xfs_da_state_t *state, int *result) { xfs_da_state_blk_t *blk; xfs_da_blkinfo_t *curr; xfs_da_intnode_t *node; xfs_da_node_entry_t *btree; xfs_dablk_t blkno; int probe, span, max, error, retval; xfs_dahash_t hashval, btreehashval; xfs_da_args_t *args; args = state->args; /* * Descend thru the B-tree searching each level for the right * node to use, until the right hashval is found. */ blkno = (args->whichfork == XFS_DATA_FORK)? state->mp->m_dirleafblk : 0; for (blk = &state->path.blk[0], state->path.active = 1; state->path.active <= XFS_DA_NODE_MAXDEPTH; blk++, state->path.active++) { /* * Read the next node down in the tree. */ blk->blkno = blkno; error = xfs_da_read_buf(args->trans, args->dp, blkno, -1, &blk->bp, args->whichfork); if (error) { blk->blkno = 0; state->path.active--; return(error); } curr = blk->bp->data; blk->magic = be16_to_cpu(curr->magic); ASSERT(blk->magic == XFS_DA_NODE_MAGIC || blk->magic == XFS_DIR2_LEAFN_MAGIC || blk->magic == XFS_ATTR_LEAF_MAGIC); /* * Search an intermediate node for a match. */ if (blk->magic == XFS_DA_NODE_MAGIC) { node = blk->bp->data; max = be16_to_cpu(node->hdr.count); blk->hashval = be32_to_cpu(node->btree[max-1].hashval); /* * Binary search. (note: small blocks will skip loop) */ probe = span = max / 2; hashval = args->hashval; for (btree = &node->btree[probe]; span > 4; btree = &node->btree[probe]) { span /= 2; btreehashval = be32_to_cpu(btree->hashval); if (btreehashval < hashval) probe += span; else if (btreehashval > hashval) probe -= span; else break; } ASSERT((probe >= 0) && (probe < max)); ASSERT((span <= 4) || (be32_to_cpu(btree->hashval) == hashval)); /* * Since we may have duplicate hashval's, find the first * matching hashval in the node. */ while ((probe > 0) && (be32_to_cpu(btree->hashval) >= hashval)) { btree--; probe--; } while ((probe < max) && (be32_to_cpu(btree->hashval) < hashval)) { btree++; probe++; } /* * Pick the right block to descend on. */ if (probe == max) { blk->index = max-1; blkno = be32_to_cpu(node->btree[max-1].before); } else { blk->index = probe; blkno = be32_to_cpu(btree->before); } } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) { blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL); break; } else if (blk->magic == XFS_DIR2_LEAFN_MAGIC) { blk->hashval = xfs_dir2_leafn_lasthash(blk->bp, NULL); break; } } /* * A leaf block that ends in the hashval that we are interested in * (final hashval == search hashval) means that the next block may * contain more entries with the same hashval, shift upward to the * next leaf and keep searching. */ for (;;) { if (blk->magic == XFS_DIR2_LEAFN_MAGIC) { retval = xfs_dir2_leafn_lookup_int(blk->bp, args, &blk->index, state); } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) { retval = xfs_attr_leaf_lookup_int(blk->bp, args); blk->index = args->index; args->blkno = blk->blkno; } else { ASSERT(0); return XFS_ERROR(EFSCORRUPTED); } if (((retval == ENOENT) || (retval == ENOATTR)) && (blk->hashval == args->hashval)) { error = xfs_da_path_shift(state, &state->path, 1, 1, &retval); if (error) return(error); if (retval == 0) { continue; } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) { /* path_shift() gives ENOENT */ retval = XFS_ERROR(ENOATTR); } } break; } *result = retval; return(0); } /*======================================================================== * Utility routines. *========================================================================*/ /* * Link a new block into a doubly linked list of blocks (of whatever type). */ int /* error */ xfs_da_blk_link(xfs_da_state_t *state, xfs_da_state_blk_t *old_blk, xfs_da_state_blk_t *new_blk) { xfs_da_blkinfo_t *old_info, *new_info, *tmp_info; xfs_da_args_t *args; int before=0, error; xfs_dabuf_t *bp; /* * Set up environment. */ args = state->args; ASSERT(args != NULL); old_info = old_blk->bp->data; new_info = new_blk->bp->data; ASSERT(old_blk->magic == XFS_DA_NODE_MAGIC || old_blk->magic == XFS_DIR2_LEAFN_MAGIC || old_blk->magic == XFS_ATTR_LEAF_MAGIC); ASSERT(old_blk->magic == be16_to_cpu(old_info->magic)); ASSERT(new_blk->magic == be16_to_cpu(new_info->magic)); ASSERT(old_blk->magic == new_blk->magic); switch (old_blk->magic) { case XFS_ATTR_LEAF_MAGIC: before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp); break; case XFS_DIR2_LEAFN_MAGIC: before = xfs_dir2_leafn_order(old_blk->bp, new_blk->bp); break; case XFS_DA_NODE_MAGIC: before = xfs_da_node_order(old_blk->bp, new_blk->bp); break; } /* * Link blocks in appropriate order. */ if (before) { /* * Link new block in before existing block. */ new_info->forw = cpu_to_be32(old_blk->blkno); new_info->back = old_info->back; if (old_info->back) { error = xfs_da_read_buf(args->trans, args->dp, be32_to_cpu(old_info->back), -1, &bp, args->whichfork); if (error) return(error); ASSERT(bp != NULL); tmp_info = bp->data; ASSERT(be16_to_cpu(tmp_info->magic) == be16_to_cpu(old_info->magic)); ASSERT(be32_to_cpu(tmp_info->forw) == old_blk->blkno); tmp_info->forw = cpu_to_be32(new_blk->blkno); xfs_da_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1); xfs_da_buf_done(bp); } old_info->back = cpu_to_be32(new_blk->blkno); } else { /* * Link new block in after existing block. */ new_info->forw = old_info->forw; new_info->back = cpu_to_be32(old_blk->blkno); if (old_info->forw) { error = xfs_da_read_buf(args->trans, args->dp, be32_to_cpu(old_info->forw), -1, &bp, args->whichfork); if (error) return(error); ASSERT(bp != NULL); tmp_info = bp->data; ASSERT(tmp_info->magic == old_info->magic); ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno); tmp_info->back = cpu_to_be32(new_blk->blkno); xfs_da_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1); xfs_da_buf_done(bp); } old_info->forw = cpu_to_be32(new_blk->blkno); } xfs_da_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1); xfs_da_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1); return(0); } /* * Compare two intermediate nodes for "order". */ STATIC int xfs_da_node_order(xfs_dabuf_t *node1_bp, xfs_dabuf_t *node2_bp) { xfs_da_intnode_t *node1, *node2; node1 = node1_bp->data; node2 = node2_bp->data; ASSERT((be16_to_cpu(node1->hdr.info.magic) == XFS_DA_NODE_MAGIC) && (be16_to_cpu(node2->hdr.info.magic) == XFS_DA_NODE_MAGIC)); if ((be16_to_cpu(node1->hdr.count) > 0) && (be16_to_cpu(node2->hdr.count) > 0) && ((be32_to_cpu(node2->btree[0].hashval) < be32_to_cpu(node1->btree[0].hashval)) || (be32_to_cpu(node2->btree[be16_to_cpu(node2->hdr.count)-1].hashval) < be32_to_cpu(node1->btree[be16_to_cpu(node1->hdr.count)-1].hashval)))) { return(1); } return(0); } /* * Pick up the last hashvalue from an intermediate node. */ STATIC uint xfs_da_node_lasthash(xfs_dabuf_t *bp, int *count) { xfs_da_intnode_t *node; node = bp->data; ASSERT(be16_to_cpu(node->hdr.info.magic) == XFS_DA_NODE_MAGIC); if (count) *count = be16_to_cpu(node->hdr.count); if (!node->hdr.count) return(0); return be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1].hashval); } /* * Unlink a block from a doubly linked list of blocks. */ STATIC int /* error */ xfs_da_blk_unlink(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk, xfs_da_state_blk_t *save_blk) { xfs_da_blkinfo_t *drop_info, *save_info, *tmp_info; xfs_da_args_t *args; xfs_dabuf_t *bp; int error; /* * Set up environment. */ args = state->args; ASSERT(args != NULL); save_info = save_blk->bp->data; drop_info = drop_blk->bp->data; ASSERT(save_blk->magic == XFS_DA_NODE_MAGIC || save_blk->magic == XFS_DIR2_LEAFN_MAGIC || save_blk->magic == XFS_ATTR_LEAF_MAGIC); ASSERT(save_blk->magic == be16_to_cpu(save_info->magic)); ASSERT(drop_blk->magic == be16_to_cpu(drop_info->magic)); ASSERT(save_blk->magic == drop_blk->magic); ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) || (be32_to_cpu(save_info->back) == drop_blk->blkno)); ASSERT((be32_to_cpu(drop_info->forw) == save_blk->blkno) || (be32_to_cpu(drop_info->back) == save_blk->blkno)); /* * Unlink the leaf block from the doubly linked chain of leaves. */ if (be32_to_cpu(save_info->back) == drop_blk->blkno) { save_info->back = drop_info->back; if (drop_info->back) { error = xfs_da_read_buf(args->trans, args->dp, be32_to_cpu(drop_info->back), -1, &bp, args->whichfork); if (error) return(error); ASSERT(bp != NULL); tmp_info = bp->data; ASSERT(tmp_info->magic == save_info->magic); ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno); tmp_info->forw = cpu_to_be32(save_blk->blkno); xfs_da_log_buf(args->trans, bp, 0, sizeof(*tmp_info) - 1); xfs_da_buf_done(bp); } } else { save_info->forw = drop_info->forw; if (drop_info->forw) { error = xfs_da_read_buf(args->trans, args->dp, be32_to_cpu(drop_info->forw), -1, &bp, args->whichfork); if (error) return(error); ASSERT(bp != NULL); tmp_info = bp->data; ASSERT(tmp_info->magic == save_info->magic); ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno); tmp_info->back = cpu_to_be32(save_blk->blkno); xfs_da_log_buf(args->trans, bp, 0, sizeof(*tmp_info) - 1); xfs_da_buf_done(bp); } } xfs_da_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1); return(0); } /* * Move a path "forward" or "!forward" one block at the current level. * * This routine will adjust a "path" to point to the next block * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the * Btree, including updating pointers to the intermediate nodes between * the new bottom and the root. */ int /* error */ xfs_da_path_shift(xfs_da_state_t *state, xfs_da_state_path_t *path, int forward, int release, int *result) { xfs_da_state_blk_t *blk; xfs_da_blkinfo_t *info; xfs_da_intnode_t *node; xfs_da_args_t *args; xfs_dablk_t blkno=0; int level, error; /* * Roll up the Btree looking for the first block where our