Определение свободного и занятого места k

[McZim]

Всем привет. Помогите добрым "пинком", а то я что то запутался. В приводимом ниже коде будет все очень просто и как будто другого кода не существует, будут опущены проверки на ошибки и т.д., но главная мысль останется, (например: на открытие раздела будет передаваться конкретно заданные а не некая переменная его содержащая и т.п.).

и так код структуры супер блока ФС ReiserFS, из которой мы будем доставать, нужную нам на определенном этапе программы, информацию:

Код:

struct reiserfs_super_block
{
  uint32_t s_block_count;
  uint32_t s_free_blocks;                  /* free blocks count    */
  uint32_t s_root_block;                   /* root block number    */
  uint32_t s_journal_block;                /* journal block number    */
  uint32_t s_journal_dev;                  /* journal device number  */

  /* Since journal size is currently a #define in a header file, if
  ** someone creates a disk with a 16MB journal and moves it to a
  ** system with 32MB journal default, they will overflow their journal
  ** when they mount the disk.  s_orig_journal_size, plus some checks
  ** while mounting (inside journal_init) prevent that from happening
  */

/* great comment Chris. Thanks.  -Hans */

  uint32_t s_orig_journal_size;
  uint32_t s_journal_trans_max;           /* max number of blocks in a transaction.  */
  uint32_t s_journal_block_count;         /* total size of the journal. can change over time  */
  uint32_t s_journal_max_batch;           /* max number of blocks to batch into a trans */
  uint32_t s_journal_max_commit_age;      /* in seconds, how old can an async commit be */
  uint32_t s_journal_max_trans_age;       /* in seconds, how old can a transaction be */
  uint16_t s_blocksize;                    /* block size           */
  uint16_t s_oid_maxsize;                  /* max size of object id array, see get_objectid() commentary  */
  uint16_t s_oid_cursize;                  /* current size of object id array */
  uint16_t s_state;                        /* valid or error       */
  char s_magic[12];                     /* reiserfs magic string indicates that file system is reiserfs */
  uint32_t s_hash_function_code;           /* indicate, what hash function is being use to sort names in a directory*/
  uint16_t s_tree_height;                  /* height of disk tree */
  uint16_t s_bmap_nr;                      /* amount of bitmap blocks needed to address each block of file system */
  uint16_t s_version;                      /* I'd prefer it if this was a string,
                                           something like "3.6.4", and maybe
                                           16 bytes long mostly unused. We
                                           don't need to save bytes in the
                                           superblock. -Hans */
  uint16_t s_reserved;
  uint32_t s_inode_generation;
  char s_unused[124] ;                  /* zero filled by mkreiserfs */
} __attribute__ ((__packed__));

дальше код исполняемой программы, которая должна открыть раздел на чтение, сдвинуться на 65536 байт, прочитать супер блок и подсчитать сколько свободного а сколько занятого места на диске:

Код:

int main(int argc, char *argv)

{

    int fd = 0;
    int count = 0;
    struct reiserfs_super_block *super = (struct reiserfs_super_block*)malloc(sizeof(struct reiserfs_super_block));

    fd = open("/dev/sdb2", O_RDONLY);
    lseek(fd, 65536, 0);
    count = read(fd, super, sizeof(struct reiserfs_super_block));

return 0;

}

ок, после открытия раздела и различных проверок на ошибки, в структуре появляются разные значение, нас пока интересует super->s_bmap_nr в нем мы узнаем сколько у нас битмап блоков (у меня получилось 4). Далее нам требуется определить сколько занято места, сколько свободно. Тут мне единственно что понятно, так это то что нужно посмотреть каждый бит на наличие 0 или 1. 0-свободно, 1-занято. Но как реализовать? что то я туплю.

вот документация по которой пишу: http://p-nand-q.com/download/rfstool/reiserfs_docs.html

[Алексей++]

а чем сканирование всех битов не подходит ? Или я не понял задачу, может . Доки глянуть тут , к сожалению, щас не могу (

[McZim]

Алексей1153++, собственно да, подходит, не могу придумать реализацию, не сталкивался еще.

[Алексей++]

1) если сплошной массив байтов - то
1.1)способ подольше - перебираем все байты, в каждом байте перебираем 8 бит
1.2) способ быстрее - тоже просматриваем, но биты не перебираем, а свичем выбираем по маске число бит сразу

2) если не сплошной массив - зависит от структура массива

для сплошного щас накидаю примерчики

[Алексей++]

Код:

	const BYTE* pBufer=0;
	DWORD dwdLen=0;
	//pBufer=...
	//dwdLen=...

	//не будет учитываеться переполнение за 0xffffffff!
	//(если надо - пользуй тип __int64)
	DWORD dwdTotalZerozCount=0;


//медленный способ
{
	for(DWORD dwd=0;dwd<dwdLen;dwd++)
	{
		//считаем нулевые биты в байте
		BYTE by=~pBufer[dwd];
		for(;by;)
		{
			by>>=1;
			dwdTotalZerozCount++;
		}
	}
}

//-----------------
//способ побыстрее
{
 	for(DWORD dwd=0;dwd<dwdLen;dwd++)
	{
		//считаем нулевые биты в байте
		BYTE by=pBufer[dwd];

		switch(by&0xf0)
		{
			case _b8(0x00000000):dwdTotalZerozCount+=4;break;
			case _b8(0x00010000):dwdTotalZerozCount+=3;break;
			case _b8(0x00100000):dwdTotalZerozCount+=3;break;
			case _b8(0x00110000):dwdTotalZerozCount+=2;break;
			case _b8(0x01000000):dwdTotalZerozCount+=3;break;
			case _b8(0x01010000):dwdTotalZerozCount+=2;break;
			case _b8(0x01100000):dwdTotalZerozCount+=2;break;
			case _b8(0x01110000):dwdTotalZerozCount+=1;break;
			case _b8(0x10000000):dwdTotalZerozCount+=3;break;
			case _b8(0x10010000):dwdTotalZerozCount+=2;break;
			case _b8(0x10100000):dwdTotalZerozCount+=2;break;
			case _b8(0x10110000):dwdTotalZerozCount+=1;break;
			case _b8(0x11000000):dwdTotalZerozCount+=2;break;
			case _b8(0x11010000):dwdTotalZerozCount+=1;break;
			case _b8(0x11100000):dwdTotalZerozCount+=1;break;
			case _b8(0x11110000):dwdTotalZerozCount+=0;break;
		}

		switch(by&0x0f)
		{
			case _b8(0x00000000):dwdTotalZerozCount+=4;break;
			case _b8(0x00000001):dwdTotalZerozCount+=3;break;
			case _b8(0x00000010):dwdTotalZerozCount+=3;break;
			case _b8(0x00000011):dwdTotalZerozCount+=2;break;
			case _b8(0x00000100):dwdTotalZerozCount+=3;break;
			case _b8(0x00000101):dwdTotalZerozCount+=2;break;
			case _b8(0x00000110):dwdTotalZerozCount+=2;break;
			case _b8(0x00000111):dwdTotalZerozCount+=1;break;
			case _b8(0x00001000):dwdTotalZerozCount+=3;break;
			case _b8(0x00001001):dwdTotalZerozCount+=2;break;
			case _b8(0x00001010):dwdTotalZerozCount+=2;break;
			case _b8(0x00001011):dwdTotalZerozCount+=1;break;
			case _b8(0x00001100):dwdTotalZerozCount+=2;break;
			case _b8(0x00001101):dwdTotalZerozCount+=1;break;
			case _b8(0x00001110):dwdTotalZerozCount+=1;break;
			case _b8(0x00001111):dwdTotalZerozCount+=0;break;
		}
	}
}

[Алексей++]

ну а не нулевые биты будет:

dwdTotalNotZerozCount=dwdLen*8 - dwdTotalZerozCount;

(опять же, переполнение через 0xffffffff не учитывается)

быстрый способ можно ещё проще, кстати   , но не всегда быстрее, чер тот, который тетрадами считает

Код:

	for(DWORD dwd=0;dwd<dwdLen;dwd++)
	{
		//считаем нулевые биты в байте
		BYTE by=pBufer[dwd];

		if(~by&0x01)dwdTotalZerozCount++;
		if(~by&0x02)dwdTotalZerozCount++;
		if(~by&0x03)dwdTotalZerozCount++;
		if(~by&0x08)dwdTotalZerozCount++;
		if(~by&0x10)dwdTotalZerozCount++;
		if(~by&0x20)dwdTotalZerozCount++;
		if(~by&0x40)dwdTotalZerozCount++;
		if(~by&0x80)dwdTotalZerozCount++;
	}

но самый, в упор быстрый способ - в свмче перебрать все 256 вариантов байта (или свети их в массив, в котором заранее сопоставить количество бит в каждом значении байта).
О, кстати, последнее и сделай тогда

[McZim]

Алексей1153++, ок, спс, сейчас посмотрю.

[Алексей++]

вот, накидал структуру

Код:

struct s_BitesCountArray
{
	private:
	BYTE arrZ[256];//массив счётчиков нулевых битов

	public:
	s_BitesCountArray()
	{
		for(DWORD dwd=0;dwd<sizeof(arrZ);dwd++)
		{
			BYTE by=(BYTE)dwd;
			BYTE byZcount=0;

			if(by~&0x01)byZcount++;
			if(by~&0x02)byZcount++;
			if(by~&0x03)byZcount++;
			if(by~&0x08)byZcount++;
			if(by~&0x10)byZcount++;
			if(by~&0x20)byZcount++;
			if(by~&0x40)byZcount++;
			if(by~&0x80)byZcount++;
			arrZ[dwd]=byZcount;
		}
	}

	inline DWORD GetZerozBitzInBufer(const BYTE* pBufer,const DWORD dwdLen)
	{
		DWORD dwdTotalZerozCount=0;
		for(DWORD dwd=0;dwd<dwdLen;dwd++)
		{
			//считаем нулевые биты в байте
			dwdTotalZerozCount+=arrZ[pBufer[dwd]];
		}
		return dwdTotalZerozCount;
	}
};

создавай экземпляр s_BitesCountArray  - как глобальный или как член какого нибудь главного класса

[McZim]

так, у меня что то все поплыло, я имею ввиду в голове. Из структуры struct reiserfs_super_block, я знаю количество блоков, размер блока, и количество битовых карт. Если взять за основу структуру написанную выше struct s_BitesCountArray, то как мне что вызвать? Я запутался.

[McZim]

я так понимаю что мне в функцию GetZerozBitzInBufer, структуры s_BitesCountArray, нужно передать количество блоков ФС s_block_count из структуры struct reiserfs_super_block и указатель на BYTE arrZ[256] из структуры struct s_BitesCountArray. Или не так?

[Алексей++]

метод GetZerozBitzInBufer принимает сплошной буфер, считает в нём биты. Если буферов много - передавай по очереди, а результаты складывай


что то вроде

Код:

s_BitesCountArray global_MyCounter;

...
...

f(...)
{
  ....
  длина = global_MyCounter.GetZerozBitzInBufer(buf1, len1)
        + global_MyCounter.GetZerozBitzInBufer(buf2, len2)
        + global_MyCounter.GetZerozBitzInBufer(buf3, len3);//ну или в цикле
}

главное условие для буфера - чтобы это был сплошной буфер, байты используются целиком (ведь хвостики битов, если такие есть, тоже посчитаются). Для особых случаев перепиши метод, как нужно, я же ещё до сих пор всех условий не знаю

[McZim]

Алексей1153++, ты меня конечно извини, но как-то ты не понятно для меня пишешь

[Алексей++]

так мне условие даже ещё не понятно, говорю же

покажи пример - какие буфера будут, сколько, каково у них устройство

[McZim]

ЧАСТИЧНО РАЗОБРАЛИСЬ, СПАСИБО

[McZim]

Код:

.....
.....
.....
for(int k=0; k < super->s_bmap_nr; k++)
            {
                byte_c->GetZeroBitInBuf((REISERFS_DISK_OFFSET_IN_BYTES + (unsigned char*)super), super->s_block_count * super->s_blocksize);
            }

....
....
....
unsigned int s_BitCountArray::GetZeroBitInBuf(const unsigned char* pBuf,const unsigned int Len)
{
    unsigned int TotalZerozCount = 0;

    for(unsigend int n = 0; n < Len; n++)
    {
        TotalZerozCount += arrZ[pBuf[n]]; //считаем нулевые биты в байте
    }

return TotalZerozCount;
}

и отдельно массив

Код:

s_BitCountArray::s_BitCountArray()
{
    for(unsigned int dwd=0;dwd<sizeof(arrZ);dwd++)
    {
        unsigned char by=(unsigned char)dwd;
        unsigned char byZcount=0;

        if(by~&0x01)byZcount++;
        if(by~&0x02)byZcount++;
        if(by~&0x03)byZcount++;
        if(by~&0x08)byZcount++;
        if(by~&0x10)byZcount++;
        if(by~&0x20)byZcount++;
        if(by~&0x40)byZcount++;
        if(by~&0x80)byZcount++;

        arrZ[dwd]=byZcount;
    }
}

пока что падает по SIGSEG, но это дело в типах.

[Алексей++]

где именно падает, по какой причине ?

[McZim]

падает вот тут примерно на 61500 с копейками числе n

Код:

unsigned int s_BitCountArray::GetZeroBitInBuf(const unsigned char* pBuf,const unsigned int Len)
{
    unsigned int TotalZerozCount = 0;

    for(unsigend int n = 0; n < Len; n++)
    {
        TotalZerozCount += arrZ[pBuf[n]]; //считаем нулевые биты в байте
    }

return TotalZerozCount;
}

[Алексей++]

это нездоровая фигня, значит вылазишь в неправильную область. С этим надо осторожно: перед входом в процедуру убедись, что передаёшь правильный буфер,- адрес начала и длину.

Щас залезу по ссылке, попробую понять, что то с форматом данных ты напутал всё же )

[McZim]

Алексей1153++, я вот тоже думаю что тут именно тип данных причина.

[Алексей++]

вот сразу

The first bitmap block is one block higher than the superblock. So, to calculate the first bitmap block, you have

REISERFS_DISK_OFFSET_IN_BYTES + REISERFS_BLOCKSIZE

....

Finding the next bitmap blocks
The remaining bitmap blocks other than the first are calculated using this formula:

REISERFS_BLOCKSIZE * REISERFS_BLOCKSIZE * REISERFS_BLOCKSIZE * 8 * n

Where n is >= 1. Don't ask me why. So, for example, if the blocksize is 4096, the second bitmap block is located at 4096*4096*8*1 = 134217728 offset in bytes, which would be block 32768.

то есть посчитать для карты надо два буфера:

Код:

pBuf1= (REISERFS_DISK_OFFSET_IN_BYTES + REISERFS_BLOCKSIZE+(BYTE*)super);
dwdLen1=blocksize ;

if(blockscount>1)
{
   pBuf2= (
      REISERFS_BLOCKSIZE * REISERFS_BLOCKSIZE * REISERFS_BLOCKSIZE * 8 * 1+
           (BYTE*)super);
   dwdLen2=blocksize*(blockscount-1) ;
}

вроде так, сейчас ещё вчитаюсь

[Алексей++]

Алексей1153++, я вот тоже думаю что тут именно тип данных причина.

тип ни при чём

[Алексей++]

ну как бы всё так должно быть

Код:

__int64 totalcount=0;

BYTE* pBuf1=0;
BYTE* pBuf2=0;
DWORD dwdLen1=0;
DWORD dwdLen2=0;


for(int k=0; k < super->s_bmap_nr; k++)
{
  pBuf1= (REISERFS_DISK_OFFSET_IN_BYTES + REISERFS_BLOCKSIZE+(BYTE*)super);
  dwdLen1=blocksize ;
  totalcount+=byte_c->GetZeroBitInBuf(pBuf1,dwdLen1);


  if(blockscount>1)
  {
     pBuf2= (
        REISERFS_BLOCKSIZE * REISERFS_BLOCKSIZE * REISERFS_BLOCKSIZE * 8 * 1+
        (BYTE*)super
            );
     dwdLen2=blocksize*(blockscount-1) ;
     totalcount+=byte_c->GetZeroBitInBuf(pBuf2,dwdLen2);
  }
}

а ещё жутко терзают смутные сомнения, что должна у вас там быть специальная функция, которая это всё считает Больно уж штука такая, которая может всем понадобится. Или я ошибаюсь ?

[McZim]

Алексей1153++, в полне вероятно

[McZim]

падает там же, со значениями

n = 127440
TotalZerozCount = 11669763

[Алексей++]

в общем, затык весь в том, как передать в метод буфер для подсчёта. Вернее, как правильно определить указатели и длИны , тут нужны знатоки, я уже вряд ли дальше помогу )

[McZim]

поправочка:

TotalZerozCount = 11723425

падает после второго вхождения в эту функцию, т.е.

Код:

totalcount += byte_c->GetZeroBitInBuf(buff2,len2);

[McZim]

Алексей1153++, ок, спасибо тебе и так большое!!!

[Алексей++]

ааа, кажись я понял.

в цикле ты указатель super то не меняешь, и, видимо, попадается такой момент, когда в super блоков меньше, чем ты в данный момент считаешь - вот и вылет

[Алексей++]

ой, гоню, указатель super менят то не надо , перебирать же надо карты, и адрес брать не от начала super. А от начала

super->.... (текущая карта ) !!!

[McZim]

Алексей1153++, меня терзают смутные сомнения а не нужно ли каждый раз в цикле в хвост вот этому

Код:

buff2 = (super->s_blocksize * super->s_blocksize * super->s_blocksize * 8 * 1 + (unsigned char*)super);

добавлять * super->s_blocksize, а?

Код:

Finding the next bitmap blocks

The remaining bitmap blocks other than the first are calculated using this formula:

REISERFS_BLOCKSIZE * REISERFS_BLOCKSIZE * REISERFS_BLOCKSIZE * 8 * n

Where n is >= 1. Don't ask me why. So, for example, if the blocksize is 4096, the second bitmap block is located at 4096*4096*8*1 = 134217728 offset in bytes, which would be block 32768.