| // Copyright 2016 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| package cluster |
| |
| import ( |
| "math/rand" |
| "sync" |
| "testing" |
| "time" |
| |
| "thinfs/fs/msdosfs/bootrecord" |
| "thinfs/fs/msdosfs/testutil" |
| ) |
| |
| // Without accessing any clusters, open and close the cluster manager. |
| func TestMountUnmount(t *testing.T) { |
| fs := testutil.MkfsFAT(t, "1G", 2, 0, 4, 512) |
| defer fs.RmfsFAT() |
| dev := fs.GetDevice() |
| defer dev.Close() |
| |
| br, err := bootrecord.New(dev) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| mgr, err := Mount(dev, br, false) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| err = mgr.Unmount() |
| if err != nil { |
| t.Fatal(err) |
| } |
| } |
| |
| // Utility to quickly allocate a cluster chain and return the collected clusters. |
| func checkAllocateChain(t *testing.T, mgr *Manager, size uint32) []uint32 { |
| var err error |
| clusters := make([]uint32, size) |
| clusters[0], err = mgr.ClusterExtend(0) |
| if err != nil { |
| t.Fatal(err) |
| } |
| for i := 1; i < len(clusters); i++ { |
| clusters[i], err = mgr.ClusterExtend(clusters[i-1]) |
| if err != nil { |
| t.Fatal(err) |
| } |
| } |
| return clusters |
| } |
| |
| // Utility to quickly verify the contents of a cluster chain. |
| func checkClusterChain(t *testing.T, mgr *Manager, start uint32, goldChain []uint32) { |
| // Verify the clusters we allocated |
| collectedClusters, err := mgr.ClusterCollect(start) |
| if err != nil { |
| t.Fatal(err) |
| } else if len(collectedClusters) != len(goldChain) { |
| t.Fatalf("Unexpected ClusterCollect length %d", len(collectedClusters)) |
| } |
| for i := range goldChain { |
| if goldChain[i] != collectedClusters[i] { |
| t.Fatalf("Expected collected clusters[%d] to be %d, but it was %d", |
| i, goldChain[i], collectedClusters[i]) |
| } |
| } |
| } |
| |
| // Test basic operations on clusters. |
| func TestClusterOperationsBasic(t *testing.T) { |
| fs := testutil.MkfsFAT(t, "1G", 2, 0, 4, 512) |
| defer fs.RmfsFAT() |
| dev := fs.GetDevice() |
| defer dev.Close() |
| |
| br, err := bootrecord.New(dev) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| mgr, err := Mount(dev, br, false) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| // Allocate some clusters |
| clusters := checkAllocateChain(t, mgr, 5) |
| |
| // Verify the clusters we allocated |
| checkClusterChain(t, mgr, clusters[0], clusters) |
| |
| // Truncate the cluster chain |
| newLen := 3 |
| err = mgr.ClusterTruncate(clusters[newLen-1]) |
| if err != nil { |
| t.Fatal(err) |
| } |
| collectedClusters, err := mgr.ClusterCollect(clusters[0]) |
| if err != nil { |
| t.Fatal(err) |
| } else if len(collectedClusters) != newLen { |
| t.Fatalf("Unexpected ClusterCollect length %d", len(collectedClusters)) |
| } |
| for i := 0; i < len(collectedClusters)-1; i++ { |
| if clusters[i] != collectedClusters[i] { |
| t.Fatalf("Expected collected clusters[%d] to be %d, but it was %d", |
| i, clusters[i], collectedClusters[i]) |
| } |
| } |
| finalCluster := collectedClusters[len(collectedClusters)-1] |
| val, err := mgr.fat.Get(finalCluster) |
| if err != nil { |
| t.Fatal(err) |
| } else if val != mgr.ClusterEOF() { |
| t.Fatalf("Truncated chain at %d to be EOF, but it was %d", finalCluster, val) |
| } |
| |
| // Delete the rest of the cluster chain |
| err = mgr.ClusterDelete(clusters[0]) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| // Check that all values of the cluster have been deleted |
| for i := range clusters { |
| val, err := mgr.fat.Get(clusters[i]) |
| if err != nil { |
| t.Fatalf("Cannot read FAT cluster %d", clusters[i]) |
| } else if !mgr.fat.IsFree(val) { |
| t.Fatalf("Expected cluster %d to be free, but it was %d", clusters[i], val) |
| } |
| } |
| |
| err = mgr.Unmount() |
| if err != nil { |
| t.Fatal(err) |
| } |
| } |
| |
| // Mount, allocate some clusters, unmount, and remount as readonly. |
| // This test shows the limited capabilities of read-only access. |
| func TestClusterManagerReadonly(t *testing.T) { |
| fs := testutil.MkfsFAT(t, "1G", 2, 0, 4, 512) |
| defer fs.RmfsFAT() |
| dev := fs.GetDevice() |
| defer dev.Close() |
| |
| br, err := bootrecord.New(dev) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| mgr, err := Mount(dev, br, false) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| // Allocate some clusters and unmount. |
| clusters := checkAllocateChain(t, mgr, 5) |
| checkClusterChain(t, mgr, clusters[0], clusters) |
| err = mgr.Unmount() |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| // Remount as readonly |
| mgr, err = Mount(dev, br, true) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| // Demonstrate that we can collect the clusters |
| checkClusterChain(t, mgr, clusters[0], clusters) |
| |
| // Demonstrate that we CANNOT modify clusters |
| if _, err := mgr.ClusterExtend(clusters[4]); err == nil { |
| t.Fatal("Expected that adding clusters while in readonly mode would cause an error") |
| } else if err := mgr.ClusterDelete(clusters[0]); err == nil { |
| t.Fatal("Expected that deleting clusters while in readonly mode would cause an error") |
| } else if err := mgr.ClusterTruncate(clusters[0]); err == nil { |
| t.Fatal("Expected that truncating clusters while in readonly mode would cause an error") |
| } |
| |
| // For good measure, collect the clusters again (it would be bad if we managed to change the |
| // FAT on one of the previous error cases). |
| checkClusterChain(t, mgr, clusters[0], clusters) |
| |
| err = mgr.Unmount() |
| if err != nil { |
| t.Fatal(err) |
| } |
| } |
| |
| // Test some invalid cluster operations. |
| func TestClusterOperationsInvalid(t *testing.T) { |
| fs := testutil.MkfsFAT(t, "1G", 2, 0, 4, 512) |
| defer fs.RmfsFAT() |
| dev := fs.GetDevice() |
| defer dev.Close() |
| |
| br, err := bootrecord.New(dev) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| mgr, err := Mount(dev, br, false) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| // Allocate some clusters |
| clusters := make([]uint32, 5) |
| clusters[0], err = mgr.ClusterExtend(0) |
| if err != nil { |
| t.Fatal(err) |
| } |
| for i := 1; i < len(clusters); i++ { |
| clusters[i], err = mgr.ClusterExtend(clusters[i-1]) |
| if err != nil { |
| t.Fatal(err) |
| } |
| } |
| |
| // Extend from the middle of a cluster chain |
| _, err = mgr.ClusterExtend(clusters[1]) |
| if err == nil { |
| t.Fatal("Expected that extending from the middle of a cluster chain would cause an error") |
| } |
| |
| // Delete / Truncate using EOF / free cluster |
| if err := mgr.ClusterDelete(mgr.fat.FreeValue()); err != nil { |
| t.Fatal("Expected ClusterDelete(free) to be a no-op") |
| } else if err := mgr.ClusterDelete(mgr.fat.EOFValue()); err != nil { |
| t.Fatal("Expected ClusterDelete(EOF) to be a no-op") |
| } else if err := mgr.ClusterTruncate(mgr.fat.FreeValue()); err != nil { |
| t.Fatal("Expected ClusterTruncate(free) to be a no-op") |
| } else if err := mgr.ClusterTruncate(mgr.fat.EOFValue()); err != nil { |
| t.Fatal("Expected ClusterTruncate(EOF) to be a no-op") |
| } |
| |
| err = mgr.Unmount() |
| if err != nil { |
| t.Fatal(err) |
| } |
| } |
| |
| // Test access to cluster chains which contains loops (one of those things that should never happen). |
| func TestClusterChainLoop(t *testing.T) { |
| fs := testutil.MkfsFAT(t, "1G", 2, 0, 4, 512) |
| defer fs.RmfsFAT() |
| dev := fs.GetDevice() |
| defer dev.Close() |
| |
| br, err := bootrecord.New(dev) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| mgr, err := Mount(dev, br, false) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| // Allocate some clusters |
| clusters := make([]uint32, 5) |
| clusters[0], err = mgr.ClusterExtend(0) |
| if err != nil { |
| t.Fatal(err) |
| } |
| for i := 1; i < len(clusters); i++ { |
| clusters[i], err = mgr.ClusterExtend(clusters[i-1]) |
| if err != nil { |
| t.Fatal(err) |
| } |
| } |
| |
| // Erroneously force the last cluster to point to the first one. This makes the chain invalid. |
| if err := mgr.fat.Set(clusters[0], clusters[4]); err != nil { |
| t.Fatal(err) |
| } |
| |
| // Demonstrate that collecting the clusters results in an error (rather than an infinite loop). |
| if _, err := mgr.ClusterCollect(clusters[0]); err == nil { |
| t.Fatal("Expected that collecting a looped cluster would cause an error") |
| } |
| |
| // Demonstrate that deleting the chain results in an error (does not end in EOF). |
| if err := mgr.ClusterDelete(clusters[0]); err == nil { |
| t.Fatal("Expected that deleting chain would cause an error") |
| } |
| |
| err = mgr.Unmount() |
| if err != nil { |
| t.Fatal(err) |
| } |
| } |
| |
| // Test access to cluster manager after unmounting it. Demonstrate that no requests can actually |
| // access or modify the FAT. |
| func TestClusterUnmountedAccess(t *testing.T) { |
| fs := testutil.MkfsFAT(t, "1G", 2, 0, 4, 512) |
| defer fs.RmfsFAT() |
| dev := fs.GetDevice() |
| defer dev.Close() |
| |
| br, err := bootrecord.New(dev) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| mgr, err := Mount(dev, br, false) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| // Allocate some clusters and unmount. |
| clusters := checkAllocateChain(t, mgr, 5) |
| checkClusterChain(t, mgr, clusters[0], clusters) |
| err = mgr.Unmount() |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| // Demonstrate that we CANNOT access clusters after unmounting. |
| if _, err := mgr.ClusterCollect(clusters[0]); err == nil { |
| t.Fatal("Expected that accessing clusters while unmounted would cause an error") |
| } else if _, err := mgr.ClusterExtend(clusters[4]); err == nil { |
| t.Fatal("Expected that adding clusters while unmounted would cause an error") |
| } else if err := mgr.ClusterDelete(clusters[0]); err == nil { |
| t.Fatal("Expected that deleting clusters while unmounted would cause an error") |
| } else if err := mgr.ClusterTruncate(clusters[0]); err == nil { |
| t.Fatal("Expected that truncating clusters while unmounted would cause an error") |
| } |
| |
| // Remount as readonly; verify the clusters have not changed since we unmounted. |
| mgr, err = Mount(dev, br, true) |
| if err != nil { |
| t.Fatal(err) |
| } |
| checkClusterChain(t, mgr, clusters[0], clusters) |
| |
| err = mgr.Unmount() |
| if err != nil { |
| t.Fatal(err) |
| } |
| } |
| |
| // Test concurrent access to cluster manager by allocating and deleting cluster chains concurrently. |
| func TestClusterConcurrentAccess(t *testing.T) { |
| fs := testutil.MkfsFAT(t, "1G", 2, 0, 4, 512) |
| defer fs.RmfsFAT() |
| dev := fs.GetDevice() |
| defer dev.Close() |
| |
| br, err := bootrecord.New(dev) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| mgr, err := Mount(dev, br, false) |
| if err != nil { |
| t.Fatal(err) |
| } |
| |
| // Access to the "chainStarts" slice is locked, but access to the cluster manager itself should |
| // NOT BE LOCKED (in this test code). |
| var chainStartsLock sync.Mutex |
| var chainStarts []uint32 |
| |
| numClustersPerThread := 100 |
| |
| // Thread type 1: Allocate a large number of chains. |
| allocator := func(c chan bool) { |
| for i := 0; i < numClustersPerThread; i++ { |
| clusters := checkAllocateChain(t, mgr, 5) |
| chainStartsLock.Lock() |
| chainStarts = append(chainStarts, clusters[0]) |
| chainStartsLock.Unlock() |
| } |
| |
| c <- true |
| } |
| |
| // Thread type 2: Delete a large number of chains (equal in count to those allocated). |
| seed := time.Now().UnixNano() |
| r := rand.New(rand.NewSource(seed)) |
| deleter := func(c chan bool) { |
| for i := 0; i < numClustersPerThread; i++ { |
| for { |
| chainStartsLock.Lock() |
| if len(chainStarts) == 0 { |
| chainStartsLock.Unlock() |
| continue |
| } |
| // Choose a random chain to remove. |
| r := r.Intn(len(chainStarts)) |
| start := chainStarts[r] |
| // Delete the "start" from chainStarts |
| chainStarts[r] = chainStarts[len(chainStarts)-1] |
| chainStarts = chainStarts[:len(chainStarts)-1] |
| chainStartsLock.Unlock() |
| |
| if err := mgr.ClusterDelete(start); err != nil { |
| t.Fatal(err) |
| } |
| break |
| } |
| } |
| c <- true |
| } |
| |
| // Thread type 3: Try collecting as many clusters as possible. Errors are likely, so ignore |
| // them. |
| collector := func(c chan bool) { |
| for { |
| select { |
| case _ = <-c: // Exit once channel has been closed. |
| return |
| default: |
| chainStartsLock.Lock() |
| if len(chainStarts) == 0 { |
| chainStartsLock.Unlock() |
| continue |
| } |
| // Choose a random chain to collect. |
| r := r.Intn(len(chainStarts)) |
| start := chainStarts[r] |
| chainStartsLock.Unlock() |
| // We have unlocked the chainStarts lock! "start" may be invalid! |
| |
| clusters, err := mgr.ClusterCollect(start) |
| if err == nil && len(clusters) != 5 { |
| t.Fatal("Collector thread read invalid cluster chain") |
| } |
| |
| } |
| } |
| } |
| |
| finishChan := make(chan bool) |
| closeChan := make(chan bool) |
| numAllocatorDeleterPairs := 10 |
| |
| for i := 0; i < numAllocatorDeleterPairs; i++ { |
| go allocator(finishChan) |
| go deleter(finishChan) |
| go collector(closeChan) |
| } |
| |
| // Wait for the allocator / deleters to complete. |
| for i := 0; i < numAllocatorDeleterPairs*2; i++ { |
| <-finishChan |
| } |
| |
| // Inform the collectors they can stop. |
| close(closeChan) |
| |
| err = mgr.Unmount() |
| if err != nil { |
| t.Fatal(err) |
| } |
| } |