[haiku-commits] haiku: hrev54095 - src/add-ons/kernel/file_systems/xfs

  • From: Adrien Destugues <pulkomandy@xxxxxxxxx>
  • To: haiku-commits@xxxxxxxxxxxxx
  • Date: Mon, 27 Apr 2020 06:28:52 -0400 (EDT)

hrev54095 adds 1 changeset to branch 'master'
old head: 03f4263ea50930477c3f9a5137acd82ba8415f2a
new head: eab542ef0365c9976c912d51fbc8d28f82bf18cf
overview: 
https://git.haiku-os.org/haiku/log/?qt=range&q=eab542ef0365+%5E03f4263ea509

----------------------------------------------------------------------------

eab542ef0365: xfs: Init AG Free Space Management
  
  Currently need to make the B+Tree for AG Free Space Management.
  The functions or the code for this task isn't complete. Sharing for
  reference.
  
  Change-Id: I1e29832b9645bd527962128a8c85b7ca24c7fd50
  Reviewed-on: https://review.haiku-os.org/c/haiku/+/2378
  Reviewed-by: Adrien Destugues <pulkomandy@xxxxxxxxx>

                                    [ CruxBox <shubhambhagat111@xxxxxxxxx> ]

----------------------------------------------------------------------------

Revision:    hrev54095
Commit:      eab542ef0365c9976c912d51fbc8d28f82bf18cf
URL:         https://git.haiku-os.org/haiku/commit/?id=eab542ef0365
Author:      CruxBox <shubhambhagat111@xxxxxxxxx>
Date:        Fri Mar 20 10:20:04 2020 UTC
Committer:   Adrien Destugues <pulkomandy@xxxxxxxxx>
Commit-Date: Mon Apr 27 10:28:49 2020 UTC

----------------------------------------------------------------------------

6 files changed, 278 insertions(+), 4 deletions(-)
.../kernel/file_systems/xfs/BPlusTree.cpp        |  89 +++++++++++++
src/add-ons/kernel/file_systems/xfs/BPlusTree.h  | 131 +++++++++++++++++++
src/add-ons/kernel/file_systems/xfs/Volume.h     |   2 +-
src/add-ons/kernel/file_systems/xfs/xfs.cpp      |   5 +
src/add-ons/kernel/file_systems/xfs/xfs.h        |  53 +++++++-
src/add-ons/kernel/file_systems/xfs/xfs_types.h  |   2 +-

----------------------------------------------------------------------------

diff --git a/src/add-ons/kernel/file_systems/xfs/BPlusTree.cpp 
b/src/add-ons/kernel/file_systems/xfs/BPlusTree.cpp
new file mode 100644
index 0000000000..f199e10903
--- /dev/null
+++ b/src/add-ons/kernel/file_systems/xfs/BPlusTree.cpp
@@ -0,0 +1,89 @@
+#include "BPlusTree.h"
+
+void bplustree_short_block::SwapEndian()
+{
+       bb_magic = B_BENDIAN_TO_HOST_INT32(bb_magic);
+       bb_level = B_BENDIAN_TO_HOST_INT16(bb_level);
+       bb_numrecs = B_BENDIAN_TO_HOST_INT16(bb_numrecs);
+       bb_leftsib = B_BENDIAN_TO_HOST_INT32(bb_leftsib);
+       bb_rightsib = B_BENDIAN_TO_HOST_INT32(bb_rightsib);
+}
+
+
+void bplustree_long_block::SwapEndian()
+{
+       bb_magic = B_BENDIAN_TO_HOST_INT32(bb_magic);
+       bb_level = B_BENDIAN_TO_HOST_INT16(bb_level);
+       bb_numrecs = B_BENDIAN_TO_HOST_INT16(bb_numrecs);
+       bb_leftsib = B_BENDIAN_TO_HOST_INT64(bb_leftsib);
+       bb_rightsib = B_BENDIAN_TO_HOST_INT64(bb_rightsib);
+}
+
+
+void xfs_alloc_rec::SwapEndian()
+{
+       ar_startblock = B_BENDIAN_TO_HOST_INT32(ar_startblock);
+       ar_blockcount =  B_BENDIAN_TO_HOST_INT32(ar_blockcount);
+}
+
+
+uint32 BPlusTree::BlockSize(){
+       return fVolume.SuperBlock().BlockSize();
+}
+
+
+int BPlusTree::RecordSize(){
+       if (fRecType == ALLOC_FLAG)
+               return XFS_ALLOC_REC_SIZE;
+}
+
+
+int BPlusTree::MaxRecords(bool leaf){
+       int blockLen = BlockSize();
+       
+       if (fPtrType == SHORT_BLOCK_FLAG)
+               blockLen - XFS_BTREE_SBLOCK_SIZE;
+
+       if (leaf){
+               if (fRecType == ALLOC_FLAG)
+                       return blockLen/sizeof(xfs_alloc_rec_t);
+       }
+       else {
+               if (fKeyType) == ALLOC_FLAG){
+                       return blockLen/(sizeof(xfs_alloc_key_t)
+                                                       + 
sizeof(xfs_alloc_ptr_t));
+               }
+       }
+}
+
+
+int BPlusTree::KeyLen(){
+       if (fKeyType == ALLOC_FLAG) return XFS_ALLOC_REC_SIZE;
+}
+
+
+int BPlusTree::BlockLen(){
+       if(fPtrType == LONG_BLOCK_FLAG) return XFS_BTREE_LBLOCK_SIZE;
+       else return XFS_BTREE_SBLOCK_SIZE;
+}
+
+
+int BPlusTree::PtrLen(){
+       if(fPtrType == LONG_BLOCK_FLAG) return sizeof(uint64);
+       else return sizeof(uint32);
+}
+
+
+int BPlusTree::RecordOffset(int pos){
+       return BlockLen() + (pos-1)*RecordSize();
+}
+
+
+int BPlusTree::KeyOffset(int pos){
+       return BlockLen() + (pos-1)*KeyLen();
+}
+
+
+int BPlusTree::PtrOffset(int pos, int level){
+       return BlockLen() + MaxRecords(level>0)*KeyLen() + (pos-1)*PtrLen();
+}
diff --git a/src/add-ons/kernel/file_systems/xfs/BPlusTree.h 
b/src/add-ons/kernel/file_systems/xfs/BPlusTree.h
new file mode 100644
index 0000000000..d9e0828b20
--- /dev/null
+++ b/src/add-ons/kernel/file_systems/xfs/BPlusTree.h
@@ -0,0 +1,131 @@
+#ifndef _BPLUS_TREE_H_
+#define _BPLUS_TREE_H_
+
+#include "system_dependencies.h"
+
+/* Allocation B+ Tree Format */
+#define XFS_ABTB_MAGICNUM 0x41425442   // For block offset B+Tree
+#define XFS_ABTC_MAGICNUM 0x41425443   // For block count B+ Tree
+
+
+/* Header for Short Format btree */
+#define XFS_BTREE_SBLOCK_SIZE  18
+
+/*
+* Headers are the "nodes" really and are called "blocks". The records, keys and
+* pts are calculated using helpers
+*/
+
+struct bplustree_short_block {
+                       uint32                          bb_magic;
+                       uint16                          bb_level;
+                       uint16                          bb_numrecs;
+                       uint32                          bb_leftsib;
+                       uint32                          bb_rightsib;
+
+                       void                            SwapEndian();
+
+                       uint32                          Magic()
+                                                               { return 
bb_magic; }
+                       
+                       uint16                          Level()
+                                                               { return 
bb_level; }
+
+                       uint16                          NumRecs()
+                                                               { return 
bb_numrecs; }
+
+                       xfs_alloc_ptr_t         Left()
+                                                               { return 
bb_leftsib; }
+
+                       xfs_alloc_ptr_t         Right()
+                                                               { return 
bb_rightsib;}
+}
+
+
+/* Header for Long Format btree */
+#define XFS_BTREE_LBLOCK_SIZE  24
+struct bplustree_long_block {
+                       uint32                          bb_magic;
+                       uint16                          bb_level;
+                       uint16                          bb_numrecs;
+                       uint64                          bb_leftsib;
+                       uint64                          bb_rightsib;
+
+                       void                            SwapEndian();
+
+                       uint32                          Magic()
+                                                               { return 
bb_magic; }
+
+                       uint16                          Level()
+                                                               { return 
bb_level; }
+
+                       uint16                          NumRecs()
+                                                               { return 
bb_numrecs; }
+
+                       xfs_alloc_ptr_t         Left()
+                                                               { return 
bb_leftsib; }
+
+                       xfs_alloc_ptr_t         Right()
+                                                               { return 
bb_rightsib;}
+}
+
+
+/* Array of these records in the leaf node along with above headers */
+#define XFS_ALLOC_REC_SIZE     8
+typedef struct xfs_alloc_rec {
+                       uint32                          ar_startblock;
+                       uint32                          ar_blockcount;
+
+                       void                            SwapEndian();
+
+                       uint32                          StartBlock()
+                                                               { return 
ar_startblock; }
+
+                       uint32                          BlockCount()
+                                                               { return 
ar_blockcount; }
+
+} xfs_alloc_rec_t, xfs_alloc_key_t;
+
+// Swap Endians while returning itself
+typedef uint32 xfs_alloc_ptr_t;        //  Node pointers, AG relative block 
pointer
+
+#define ALLOC_FLAG 0x1
+
+#define LONG_BLOCK_FLAG 0x1
+#define SHORT_BLOCK_FLAG 0x2
+
+union btree_ptr {
+       bplustree_long_block fLongBlock;
+       bplustree_short_block fShortBlock;
+}
+
+union btree_key {
+       xfs_alloc_key_t fAlloc;
+}
+
+union btree_rec {
+       xfs_alloc_rec_t fAlloc;
+}
+
+class BPlusTree {
+       public:
+                       uint32                          BlockSize();
+                       int                                     RecordSize();
+                       int                                     MaxRecords(bool 
leaf);
+                       int                                     KeyLen();
+                       int                                     BlockLen();
+                       int                                     PtrLen();
+                       int                                     
RecordOffset(int pos); // get the pos'th record
+                       int                                     KeyOffset(int 
pos); // get the pos'th key
+                       int                                     PtrOffset(int 
pos); // get the pos'th ptr
+
+       private:
+                       Volume*                         fVolume;
+                       xfs_agnumber_t          fAgnumber;
+                       btree_ptr*                      fRoot;
+                       int                                     fRecType;
+                       int                                     fKeyType;
+                       int                                     fPtrType;
+}
+
+#endif
diff --git a/src/add-ons/kernel/file_systems/xfs/Volume.h 
b/src/add-ons/kernel/file_systems/xfs/Volume.h
index 748eb10329..f008476404 100644
--- a/src/add-ons/kernel/file_systems/xfs/Volume.h
+++ b/src/add-ons/kernel/file_systems/xfs/Volume.h
@@ -61,4 +61,4 @@ protected:
                        uint32                          fFlags;
 };
 
-#endif
\ No newline at end of file
+#endif
diff --git a/src/add-ons/kernel/file_systems/xfs/xfs.cpp 
b/src/add-ons/kernel/file_systems/xfs/xfs.cpp
index 616290c070..e397b0b93e 100644
--- a/src/add-ons/kernel/file_systems/xfs/xfs.cpp
+++ b/src/add-ons/kernel/file_systems/xfs/xfs.cpp
@@ -11,6 +11,11 @@ XfsSuperBlock::IsValid()
 {
        if (sb_magicnum != XFS_SB_MAGIC) return false;
 
+       if (BBLOCKSIZE <= sb_blocksize){
+               ERROR("Basic block is less than 512 bytes!");
+               return false;
+       }
+       
        return true;
 }
 
diff --git a/src/add-ons/kernel/file_systems/xfs/xfs.h 
b/src/add-ons/kernel/file_systems/xfs/xfs.h
index a1d6e6fabc..633611d4cc 100644
--- a/src/add-ons/kernel/file_systems/xfs/xfs.h
+++ b/src/add-ons/kernel/file_systems/xfs/xfs.h
@@ -3,6 +3,12 @@
  * All rights reserved. Distributed under the terms of the MIT License.
  */
 
+/*
+Important:
+All fields in XFS metadata structures are in big-endian byte order
+except for log items which are formatted in host order.
+*/
+
 #ifndef _XFS_SB_H_
 #define _XFS_SB_H_
 
@@ -11,7 +17,8 @@
 
 #define XFS_SB_MAGIC 0x58465342 /* Identifies XFS. "XFSB" */
 #define XFS_SB_MAXSIZE 512
-
+#define BBLOCKLOG 9            /* Log of block size should be 9 */
+#define BBLOCKSIZE 1<<BBLOCKLOG                /* The size of a basic block 
should be 512 */
 
 
 /*     Version 4 superblock definition */
@@ -126,4 +133,46 @@ Superblock quota flags - sb_qflags
 #define XFS_SB_VERSION2_PROJID32BIT 0x0008     /* 32-bit project id */
 #define XFS_SB_VERSION2_CRCBIT 0x0010          /* Metadata checksumming */
 #define XFS_SB_VERSION2_FTYPE 0x0020
-#endif
\ No newline at end of file
+
+
+/* AG Free Space Block */
+
+/* 
+index 0 for free space B+Tree indexed by block number
+index 1 for free space B+Tree indexed by extent size
+
+Version 5 has XFS_BT_NUM_AGF defined as 3. This is because the index 2 is
+for reverse-mapped B+Trees. I have spare0/1 defined here instead.
+*/
+
+#define XFS_BTNUM_AGF 2
+#define XFS_AG_MAGICNUM 0x58414746
+class AGFreeSpace{
+       public:
+                       void                    SwapEndian();
+       private:
+                       uint32                  magicnum;
+                       uint32                  versionnum;             // 
should be set to 1
+                       uint32                  seqno;  // defines the ag 
number for the sector
+                       uint32                  length; // size of ag in fs 
blocks
+                       uint32                  roots[XFS_BTNUM_AGF];   // 
roots of trees
+                       uint32                  spare0;         //spare
+                       uint32                  levels[XFS_BTNUM_AGF];  // tree 
levels
+                       uint32                  spare1;         //spare
+                       uint32                  flfirst;        // index to 
first free list block
+                       uint32                  fllast;         // index to 
last free list block
+                       uint32                  flcount;        // number of 
blocks in freelist
+                       uint32                  freeblks;       // current num 
of free blocks in AG
+                       uint32                  longest;        // no.of blocks 
of longest
+                                                                               
        // contiguous free space in the AG
+
+                       /*number of blocks used for the free space B+trees.
+                       This is only used if the XFS_SB_VERSION2_LAZYSBCOUNTBIT
+                       bit is set in sb_features2
+                       */
+
+                       uint32                  btreeblks;
+}
+
+
+#endif
diff --git a/src/add-ons/kernel/file_systems/xfs/xfs_types.h 
b/src/add-ons/kernel/file_systems/xfs/xfs_types.h
index a2940bfcfc..3b1fd6e379 100644
--- a/src/add-ons/kernel/file_systems/xfs/xfs_types.h
+++ b/src/add-ons/kernel/file_systems/xfs/xfs_types.h
@@ -38,4 +38,4 @@ typedef int64 xfs_fsize_t;            // byte size of a file
 
 // typedef unsigned char uuid_t[16];
 
-#endif
\ No newline at end of file
+#endif


Other related posts: