search

littlefs-project / littlefs

A little fail-safe filesystem designed for microcontrollers
BSD 3-Clause "New" or "Revised" License
5.25k stars 803 forks source link

Write the detect cycles function as a function to optimize code #1013

Open wdfk-prog opened 4 months ago

wdfk-prog commented 4 months ago
wdfk-prog commented 4 months ago

Also worth mentioning is the use of gcc and makefiles on Windows; Can only compile and clear, view the overall occupancy size and generate assembly files, other operations can not take effect, will give an error; Is there any plan to support this part on Windows.

wdfk-prog commented 4 months ago
wdfk-prog commented 3 months ago

The minor style stuff aside, I think there's a slight problem with that algorithm as it changes behaviour by moving the initialization part into the loop. This might still find trivial cases of loops, but will hide loops, that need the iteration behaviour of advancing the tortoises. You can check this by noticing that several of the assignments of the function lfs_detect_cycles are now dead stores, when previously they would be re-used in the next loop iteration. Nonetheless, centralizing this check pattern may allow code size reduction.撇开次要风格的东西不谈，我认为该算法存在一个小问题，因为它通过将初始化部分移动到循环中来改变行为。这仍然可能找到循环的微不足道的情况，但会隐藏循环，这些循环需要推进的迭代行为。您可以通过注意到函数lfs_detect_cycles的几个赋值现在是死存储来检查这一点，而以前它们将在下一次循环迭代中重用。尽管如此，集中管理此检查模式可能会减小代码大小。

To fix that bug, the following should be done:要修复该错误，应执行以下操作：

  1. Introduce a structure to hold the state of the algorithm引入一个结构来保存算法的状态
typedef struct lfs_tortoise {
    lfs_block_t block[2]; // Previously tortoise
    lfs_size_t i; // Previously tortoise_i
    lfs_size_t period; // Previously tortoise_period
} lfs_tortoise_t;
  1. Pass a lfs_tortoise_t* as the second argument to 将 lfs_tortoise_t* 作为第二个参数传递给lfs_detect_cycles
  2. On the call sites: Outside the loop initialize a lfs_tortoise_t like so:在调用站点上：在循环外初始化一个lfs_tortoise_t，如下所示：
lfs_tortoise_t tortoise = {
    .block = {LFS_BLOCK_NULL, LFS_BLOCK_NULL},
    .i = 1,
    .period = 1,
};
  1. Pass that variable to lfs_detect_cycles by reference.通过引用将该变量传递给 lfs_detect_cycles。

The "cancelled" CI jobs were likely due to some loop in the filesystem under test not being detected after your change.“已取消”的 CI 作业可能是由于在更改后未检测到所测试文件系统中的某些循环。

The minor style stuff aside, I think there's a slight problem with that algorithm as it changes behaviour by moving the initialization part into the loop. This might still find trivial cases of loops, but will hide loops, that need the iteration behaviour of advancing the tortoises. You can check this by noticing that several of the assignments of the function lfs_detect_cycles are now dead stores, when previously they would be re-used in the next loop iteration. Nonetheless, centralizing this check pattern may allow code size reduction.

To fix that bug, the following should be done:

  1. Introduce a structure to hold the state of the algorithm
typedef struct lfs_tortoise {
    lfs_block_t block[2]; // Previously tortoise
    lfs_size_t i; // Previously tortoise_i
    lfs_size_t period; // Previously tortoise_period
} lfs_tortoise_t;
  1. Pass a lfs_tortoise_t* as the second argument to lfs_detect_cycles
  2. On the call sites: Outside the loop initialize a lfs_tortoise_t like so:
lfs_tortoise_t tortoise = {
    .block = {LFS_BLOCK_NULL, LFS_BLOCK_NULL},
    .i = 1,
    .period = 1,
};
  1. Pass that variable to lfs_detect_cycles by reference.

The "cancelled" CI jobs were likely due to some loop in the filesystem under test not being detected after your change.

Thank you for reminding me that I made a stupid mistake

geky-bot commented 3 months ago
Tests passed ✓, Code: 17096 B (+0.2%), Stack: 1448 B (+0.6%), Structs: 812 B (+0.0%) | | Code | Stack | Structs | | Coverage | |:--|-----:|------:|--------:|:--|---------:| | Default | 17096 B (+0.2%) | 1448 B (+0.6%) | 812 B (+0.0%) | Lines | 2373/2548 lines (+0.1%) | | Readonly | 6190 B (-0.1%) | 448 B (+0.0%) | 812 B (+0.0%) | Branches | 1241/1580 branches (-0.1%) | | Threadsafe | 17956 B (+0.2%) | 1448 B (+0.6%) | 820 B (+0.0%) | | **Benchmarks** | | Multiversion | 17164 B (+0.2%) | 1448 B (+0.6%) | 816 B (+0.0%) | Readed | 29369693876 B (+0.0%) | | Migrate | 18788 B (+0.1%) | 1744 B (+0.0%) | 816 B (+0.0%) | Proged | 1482874766 B (+0.0%) | | Error-asserts | 17780 B (+0.2%) | 1440 B (+0.6%) | 812 B (+0.0%) | Erased | 1568888832 B (+0.0%) |
geky commented 2 months ago

Also worth mentioning is the use of gcc and makefiles on Windows; Can only compile and clear, view the overall occupancy size and generate assembly files, other operations can not take effect, will give an error; Is there any plan to support this part on Windows.

Unfortunately Windows is a difficult platform to support as a development environment. It's just not worth supporting vs leveraging all of the useful tools that are available in Linux.

The best option would be use either a virtual machine or WSL to run a Linux image on windows and develop inside that. I've heard good things about WSL but haven't used it myself.

geky commented 2 months ago

Sorry, this failure was an issue on our side. GitHub made a breaking change to their APIs recently.

To fix the pr this needs to be rebased onto the devel branch: https://github.com/littlefs-project/littlefs/tree/devel, let me know if you want me to do that for you:

$ git rebase origin/devel
wdfk-prog commented 2 months ago

Sorry, this failure was an issue on our side. GitHub made a breaking change to their APIs recently.很抱歉，此失败是我们这边的问题。GitHub 最近对其 API 进行了重大更改。

To fix the pr this needs to be rebased onto the devel branch: https://github.com/littlefs-project/littlefs/tree/devel, let me know if you want me to do that for you:要修复 pr，这需要重新基到 devel 分支上：https://github.com/littlefs-project/littlefs/tree/devel，如果您希望我为您执行此操作，请告诉我：

$ git rebase origin/devel

OK

geky commented 1 month ago

Sorry again, I was having problems pushing to your branch and couldn't understand why. You set "Maintainers are allowed to edit this pull request." correctly but pushes are still being rejected for some reason.

And wow, I think this is a real mess up on GitHub's part. There is apparently a bug where cross-organization forks can't be edited by maintainers, and I think this might also be affecting forks-of-cross-org-forks: https://github.com/orgs/community/discussions/5634

So unfortunately it looks like you either need to add me as a collaborator or do the rebase locally... Fortunately it's a simple rebase with no conflicts.

wdfk-prog commented 1 month ago

Sorry again, I was having problems pushing to your branch and couldn't understand why. You set "Maintainers are allowed to edit this pull request." correctly but pushes are still being rejected for some reason.

And wow, I think this is a real mess up on GitHub's part. There is apparently a bug where cross-organization forks can't be edited by maintainers, and I think this might also be affecting forks-of-cross-org-forks: https://github.com/orgs/community/discussions/5634

So unfortunately it looks like you either need to add me as a collaborator or do the rebase locally... Fortunately it's a simple rebase with no conflicts.

geky-bot commented 1 month ago
Tests passed ✓, Code: 17000 B (-0.9%), Stack: 1440 B (+0.0%), Structs: 812 B (+0.0%) | | Code | Stack | Structs | | Coverage | |:--|-----:|------:|--------:|:--|---------:| | Default | 17000 B (-0.4%) | 1440 B (+0.0%) | 812 B (+0.0%) | Lines | 2373/2548 lines | | Readonly | 6198 B (+0.1%) | 448 B (+0.0%) | 812 B (+0.0%) | Branches | 1241/1580 branches | | Threadsafe | 17860 B (-0.4%) | 1440 B (+0.0%) | 820 B (+0.0%) | | **Benchmarks** | | Multiversion | 17072 B (-0.3%) | 1440 B (+0.0%) | 816 B (+0.0%) | Readed | 29369693876 B | | Migrate | 18688 B (-0.4%) | 1736 B (-0.5%) | 816 B (+0.0%) | Proged | 1482874766 B | | Error-asserts | 17680 B (-0.4%) | 1432 B (+0.0%) | 812 B (+0.0%) | Erased | 1568888832 B |
geky commented 1 month ago

Looks good here, thanks for that. I've manually updated the bot comment since it's still a bit broken on our end.

geky commented 1 month ago

I left some review comments, mostly related to style/consistency with the rest of the codebase.

But this looks good to me and we can probably bring it in on the next minor release.

wdfk-prog commented 1 month ago

I left some review comments, mostly related to style/consistency with the rest of the codebase.

But this looks good to me and we can probably bring it in on the next minor release.

geky-bot commented 1 month ago
Tests passed ✓, Code: 17004 B, Stack: 1440 B, Structs: 812 B | | Code | Stack | Structs | | Coverage | |:--|-----:|------:|--------:|:--|---------:| | Default | 17004 B | 1440 B | 812 B | Lines | 2378/2553 lines | | Readonly | 6202 B | 448 B | 812 B | Branches | 1241/1580 branches | | Threadsafe | 17864 B | 1440 B | 820 B | | **Benchmarks** | | Multiversion | 17076 B | 1440 B | 816 B | Readed | 29369693876 B | | Migrate | 18692 B | 1736 B | 816 B | Proged | 1482874766 B | | Error-asserts | 17684 B | 1432 B | 812 B | Erased | 1568888832 B |
geky commented 1 month ago

Thanks for making those changes. This looks good to me and will bring it in next release.

maybe it should be marked with some normative information in the pr content;

Point taken, it is a waste of both your time and my time commenting on style inconsistencies.

It is recommended to use a formatted script before submitting, such as the following link:https://github.com/mysterywolf/formatting

I had looked into astyle before, but struggled to make it do what I wanted. It was very opinionated about unnecessary things.

But a custom python script is a good idea, maybe that's the way to go.